\(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs

DOI10.1007/s00453-014-9921-5zbMath1330.68090arXiv1310.8313OpenAlexW3122637813MaRDI QIDQ747619

Mario Valencia-Pabon, Oliver Schaudt, Maya Jakobine Stein, Flavia Bonomo-Braberman

Publication date: 19 October 2015

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.8313

zbMATH Keywords

NP-hardness\(b\)-coloringco-triangle-free graphspolytime dynamic programming algorithmsstability number twotree cographs\(b\)-chromatic number of graphs with stability number twopolynomial time dynamic programming algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

A comparison of the Grundy and b-chromatic number of \(K_{2,t}\)-free graphs

Cites Work

• Unnamed Item
• On minimally \(b\)-imperfect graphs
• On the b-coloring of cographs and \(P_{4}\)-sparse graphs
• Strong tree-cographs are Birkhoff graphs
• The b-chromatic number of a graph
• \(b\)-coloring of tight graphs
• Achromatic number is NP-complete for cographs and interval graphs
• On the \(b\)-dominating coloring of graphs
• TWO THEOREMS IN GRAPH THEORY
• Edge Dominating Sets in Graphs
• Paths, Trees, and Flowers
• Discrete-Variable Extremum Problems
• The achromatic number of a graph

This page was built for publication: \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs