More about subcolorings

DOI10.1007/S00607-002-1461-1zbMATH Open1239.05060DBLPjournals/computing/BroersmaFNW02OpenAlexW2117848356WikidataQ56428501 ScholiaQ56428501MaRDI QIDQ424720FDOQ424720

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

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

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)

Cited In (14)

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

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)