On the b-coloring of cographs and \(P_{4}\)-sparse graphs

DOI10.1007/s00373-008-0829-1zbMath1221.05128OpenAlexW2051593055MaRDI QIDQ1043801

Frédéric Maffray, Javier Marenco, Guillermo Durán, Mario Valencia-Pabon, Flavia Bonomo-Braberman

Publication date: 9 December 2009

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-008-0829-1

zbMATH Keywords

cographsb-coloring\(P _{4}\)-sparse graphsb-continuityb-monotonicity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

On b-vertex and b-edge critical graphs, \(b\)-continuity and the lexicographic product of graphs, The b-chromatic number of cubic graphs, The lexicographic product of some chordal graphs and of cographs preserves \(b\)-continuity, \(b\)-chromatic sum of Mycielskian of paths, The \(b\)-chromatic number and related topics -- a survey, The \(b\)-continuity of graphs with large girth, On the \(b\)-continuity of the lexicographic product of graphs, On the \(b\)-coloring of \(P_{4}\)-tidy graphs, More results on the \(z\)-chromatic number of graphs, On quasi-monotonous graphs, A comparison of the Grundy and b-chromatic number of \(K_{2,t}\)-free graphs, On the \(b\)-chromatic number of regular graphs without 4-cycle, A characterization of edge \(b\)-critical graphs, A note on approximating the \(b\)-chromatic number, \(b\)-chromatic numbers of powers of paths and cycles, Maximization coloring problems on graphs with few \(P_4\), New bounds for the \(b\)-chromatic number of vertex deleted graphs, Graphs with large girth are \(b\)-continuous, On the b-coloring of tight graphs, \(b\)-coloring of tight graphs, On the \(b\)-chromatic number of regular graphs, b-Chromatic sum of a graph, \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs, \(b\)-coloring of Kneser graphs, b-coloring of m-tight graphs, On the \(b\)-coloring of \(G - e\), The \(b\)-chromatic index of graphs, The \(b\)-chromatic index of direct product of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On minimally \(b\)-imperfect graphs
• On b-perfect chordal graphs
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• The b-chromatic number of a graph
• On approximating the b-chromatic number
• Achromatic number is NP-complete for cographs and interval graphs
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Bounds for the b-chromatic number of some families of graphs
• On the \(b\)-dominating coloring of graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time