More about subcolorings

DOI10.1007/S00607-002-1461-1MaRDI QIDQ424720zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, J. Nešetřil, Gerhard J. Woeginger, Hajo 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

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

Recommendations

• scientific article; zbMATH DE number 1953083
• The subchromatic index of graphs
• scientific article; zbMATH DE number 2044932
• Graph Subcolorings: Complexity and Algorithms
• The NP-completeness of (1,r)-subcolorability of cubic graphs

Cited in

(14)

• scientific article; zbMATH DE number 1953083 (Why is no real title available?)
• SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
• On the algorithmic aspects of strong subcoloring
• Path-bicolorable graphs. (Extended abstract)
• On 2-Subcolourings of Chordal Graphs
• Solving partition problems almost always requires pushing many vertices around
• scientific article; zbMATH DE number 7378721 (Why is no real title available?)
• A hypocoloring model for batch scheduling
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Graph Subcolorings: Complexity and Algorithms
• On star and caterpillar arboricity
• 2-subcoloring is NP-complete for planar comparability graphs
• Path-bicolorable graphs
• scientific article; zbMATH DE number 2044932 (Why is no real title available?)

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 Q424720)