Abstract
A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to at least one vertex in each other color class. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors. This problem was introduced by Irving and Manlove (Discrete Appl Math 91:127–141, 1999), where they showed that computing b(G) is \({\mathcal {NP}}\)-hard in general and polynomial-time solvable for trees. Since then, a number of complexity results were shown, including NP-hardness results for chordal graphs (Havet et al. in Discrete Appl Math 160(18):2709–2715, 2012) and line graphs (Campos et al. in Eur J Comb 48:154–164, 2015). In this article, we present a polynomial time algorithm that solves the problem restricted to claw-free block graphs, an important subclass of chordal graphs and of line graphs. This is equivalent to solving the edge coloring version restricted to trees.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The graph terminology used in this paper follows [2].
References
Blidia, M., Maffray, F., Zemir, Z.: On b-colorings in regular graphs. Discrete Appl. Math. 157, 1787–1793 (2009)
Bondy, A., Murty, U.S.R.: Graph Theory. Springer, Berlin (2008)
Cabello, S., Jakovac, M.: On the b-chromatic number of regular graphs. Discrete Appl. Math. 159, 1303–1310 (2011)
Campos, V., Lima, C., Martins, N.A., Sampaio, L., Santos, M.C., Silva, A.: The b-chromatic index of graphs. Discrete Math. 338, 2072–2079 (2015)
Campos, V., Lima, V., Silva, A.: Graphs of girth at least 7 have high b-chromatic number. Eur. J. Comb. 48, 154–164 (2015)
Havet, F., Linhares-Sales, C., Sampaio, L.: b-Coloring of tight graphs. Discrete Appl. Math. 160(18), 2709–2715 (2012)
Irving, R.W., Manlove, D.F.: The b-chromatic number of a graph. Discrete Appl. Math. 91, 127–141 (1999)
Kouider, M., Mahéo, M.: Some bounds for the b-chromatic number of a graph. Discrete Math. 256, 267–277 (2002)
Kratochvíl, J., Tuza, ZS, Voigt, M.: On the b-Chromatic Number of Graphs. Lecture Notes in Computer Science, vol. 2573, pp. 310–320 (2002)
Marx, D.: Precoloring extension on chordal graphs. In: Graph Theory in Paris, Proceedings of a Conference in Memory of Claude Berge, pp. 255–270 (2007)
Silva, A.: Trees with small b-chromatic index. arXiv:1511.05847
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by CNPq/Brazil.
Rights and permissions
About this article
Cite this article
Campos, V., Silva, A. Edge-b-Coloring Trees. Algorithmica 80, 104–115 (2018). https://doi.org/10.1007/s00453-016-0240-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-016-0240-x