b-coloring of tight graphs

Frédéric Havet 1 Claudia Linhares Sales 2 Leonardo Sampaio 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A given k-coloring c of a graph G = (V,E) is a b-coloring if for every color class ci, 1 ≤ i ≤ k, there is a vertex colored i whose neighborhood intersects every other color class cj of c. The b-chromatic number of G is the greatest integer k such that G admits a b-coloring with k colors. A graph G is tight if it has exactly m(G) vertices of degree exactly m(G)−1, where m(G) is the largest integer m such that G has at least m vertices of degree at least m − 1. Determining the b-chromatic number of a tight graph G is NP-hard even for a connected bipartite graph [9]. In this pa- per we show that it is also NP-hard for a tight chordal graph. We also consider the particular case where the input graph is split (not necessarily tight) and show that the problem of determining the b-chromatic number is polynomial in this case. Then we define the b-closure and the partial b-closure of a tight graph, and use these concepts to give a characteriza- tion of tight graphs whose b-chromatic number is equal to m(G). This characterization is used to develop polynomial time algorithms for decid- ing whether χb(G) < m, for tight graphs that are complement of bipartite graphs, P4-sparse and block graphs. We generalize the concept of pivoted tree introduced by Irving and Manlove [6] and show its relation with the behavior of the b-chromatic number of tight graphs.
Type de document :
[Research Report] RR-7241, INRIA. 2010
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

Contributeur : Frederic Havet <>
Soumis le : lundi 20 septembre 2010 - 15:00:30
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : mardi 21 décembre 2010 - 03:01:01


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00468734, version 2


Frédéric Havet, Claudia Linhares Sales, Leonardo Sampaio. b-coloring of tight graphs. [Research Report] RR-7241, INRIA. 2010. 〈inria-00468734v2〉



Consultations de la notice


Téléchargements de fichiers