On the approximation of Min Split-coloring and Min Cocoloring

DOI10.7155/JGAA.00129MaRDI QIDQ5301394zbMATH OpenOpenAlexFDO

Authors Marc Demange, Tınaz Ekim, Dominique De Werra

Publication date 19 January 2009

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://eudml.org/doc/55401, http://www.emis.de/journals/JGAA/accepted/2006/DemangeEkimWerra2006.10.2.pdf

zbMATH Keywords

Min Split-coloringNP-hardness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximation results for the minimum graph coloring problem
• Approximation of min coloring by moderately exponential algorithms
• On split-coloring problems
• scientific article; zbMATH DE number 1839437
• On the minimum monochromatic or multicolored subgraph partition problems
• On colorings of split graphs
• Computing lower bounds for minimum sum coloring and optimum cost chromatic partition
• The complexity of minimum convex coloring
• The Complexity of Minimum Convex Coloring
• scientific article; zbMATH DE number 7561584

Cited in

(11)

• Partitioning graphs into complete and empty graphs
• Approximating minimum cocolorings.
• On approximability of optimization problems related to red/blue-split graphs
• Fixed-parameter algorithms for the cocoloring problem
• Covering Graphs by Colored Stable Sets
• scientific article; zbMATH DE number 1839437 (Why is no real title available?)
• Split-critical and uniquely split-colorable graphs
• \((p,k)\)-coloring problems in line graphs
• A tutorial on the use of graph coloring for some problems in robotics
• Approximation of min coloring by moderately exponential algorithms
• On split-coloring problems

This page was built for publication: On the approximation of Min Split-coloring and Min Cocoloring

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