More about subcolorings

DOI10.1007/3-540-36379-3_7MaRDI QIDQ4414486zbMATH OpenFDO

Authors Fedor V. Fomin, J. Nešetřil, Gerhard J. Woeginger, Hajo Broersma

Publication date 25 July 2003

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2573/25730068.htm

zbMATH Keywords

computational complexitygraph coloringpolynomial time algorithmspecial graph classessubcoloring

Mathematics Subject Classification ID

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

Recommendations

• More about subcolorings
• Graph subcolorings: Complexity and algorithms
• Graph Subcolorings: Complexity and Algorithms
• On 2-Subcolourings of Chordal Graphs
• 2-subcoloring is NP-complete for planar comparability graphs

Cited in

(5)

• On the algorithmic aspects of strong subcoloring
• 2-subcoloring is NP-complete for planar comparability graphs
• More about subcolorings
• Graph Subcolorings: Complexity and Algorithms
• Graph subcolorings: Complexity and algorithms

This page was built for publication: More about subcolorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4414486)