More about subcolorings

DOI10.1007/s00607-002-1461-1zbMath1239.05060OpenAlexW2117848356WikidataQ56428501 ScholiaQ56428501MaRDI QIDQ424720

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

Publication date: 4 June 2012

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-002-1461-1

zbMATH Keywords

computational complexitygraph coloringpolynomial time algorithmspecial graph classessubcoloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items

2-subcoloring is NP-complete for planar comparability graphs ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Unnamed Item ⋮ Path-bicolorable graphs ⋮ On the algorithmic aspects of strong subcoloring ⋮ A hypocoloring model for batch scheduling ⋮ SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS ⋮ On 2-Subcolourings of Chordal Graphs ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ On star and caterpillar arboricity ⋮ Path-Bicolorable Graphs