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 coloring c of a graph G = (V,E) is a b-coloring if in every color class there is a vertex whose neighborhood intersects every other color classes. The b-chromatic number of G, denoted χb(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 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 [15]. In this paper we show that it is also NP-hard for a tight chordal graph. We also show that the b-chromatic number of a split graph can be computed is polynomial. Then we define the b-closure and the partial b-closure of a tight graph, and use these concepts to give a characterization of tight graphs whose b-chromatic number is equal to m(G). This characterization is used to develop polynomial time algorithms for deciding whether χb(G) = m(G), 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 [12] and show its relation with the b-chromatic number of tight graphs.
Document type :
Journal articles
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00749192
Contributor : Frederic Havet <>
Submitted on : Sunday, October 23, 2016 - 4:17:30 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

File

bcoloringmtight.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00749192, version 1

Collections

Citation

Frédéric Havet, Claudia Linhares Sales, Leonardo Sampaio. b-coloring of tight graphs. Discrete Applied Mathematics, Elsevier, 2012, 160 (18), pp.2709--2715. ⟨hal-00749192⟩

Share

Metrics

Record views

282

Files downloads

158