On coloring problems with local constraints

DOI10.1016/J.ENDM.2009.11.036MaRDI QIDQ5891093zbMATH OpenOpenAlexFDO

Authors Yuri Faenza, Gianpaolo Oriolo, Flavia Bonomo

Publication date 19 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2108/7960

zbMATH Keywords

clique treescomplexity resultscomputational complexitygraph coloring problemgraph coloring problemsperfect graphsplynomial time algorithmsprecoloring extension problemunit interval graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On coloring problems with local constraints
• Between coloring and list-coloring: -coloring.
• Precoloring extension on unit interval graphs
• Exploring the complexity boundary between coloring and list-coloring
• scientific article; zbMATH DE number 1033812

Cites work

• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Approximation results for the optimum cost chromatic partition problem
• Coloring a Family of Circular Arcs
• Completely separable graphs
• Exploring the complexity boundary between coloring and list-coloring
• Generalized coloring for tree-like graphs
• scientific article; zbMATH DE number 5158493 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 772760 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Precoloring Extension III: Classes of Perfect Graphs
• Precoloring extension. I: Interval graphs
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(3)

• Locality-preserving allocations problems and coloured bin packing
• Between coloring and list-coloring: -coloring.
• On coloring problems with local constraints

This page was built for publication: On coloring problems with local constraints

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