The b-chromatic number of a graph

DOI10.1016/S0166-218X(98)00146-2zbMath0933.05051MaRDI QIDQ1283791

David F. Manlove, Robert W. Irving

Publication date: 16 December 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

partition; characterization; achromatic number; NP-complete; independent sets; b-chromatic number

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Exact values for theb-chromatic number of a power completek-ary tree, Fall colouring of bipartite graphs and Cartesian products of graphs, On \(b\)-colorings in regular graphs, A graph b-coloring framework for data clustering, On the b-coloring of cographs and \(P_{4}\)-sparse graphs, On b-perfect chordal graphs, On \(b\)-coloring of the Kneser graphs, On approximating the b-chromatic number, On the \(b\)-continuity property of graphs, Bounds for the b-chromatic number of some families of graphs, On the \(b\)-dominating coloring of graphs, The b-chromatic number of power graphs of complete caterpillars, About the b-continuity of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the minimum maximal independence number
• On approximating the minimum independent dominating set
• On the computational complexity of upper fractional domination
• Concerning the achromatic number of graphs
• Some perfect coloring properties of graphs
• Achromatic number is NP-complete for cographs and interval graphs
• Maximum versus minimum invariants for graphs
• Edge Dominating Sets in Graphs
• The achromatic number of a graph