Exploring the complexity boundary between coloring and list-coloring

DOI10.1016/j.endm.2006.06.064zbMath1134.68374OpenAlexW2008738950MaRDI QIDQ5899384

Guillermo Durán, Javier Marenco, Flavia Bonomo-Braberman

Publication date: 29 May 2007

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

Full work available at URL: https://doi.org/10.1016/j.endm.2006.06.064

zbMATH Keywords

computational complexitycoloringlist-coloring

Mathematics Subject Classification ID

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

Related Items

Solving a real-world train-unit assignment problem ⋮ Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem ⋮ Exploring the complexity boundary between coloring and list-coloring

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of completing partial Latin squares
• The ellipsoid method and its consequences in combinatorial optimization
• Some results concerning the complexity of restricted colorings of graphs
• Precoloring extension. I: Interval graphs
• Generalized coloring for tree-like graphs
• The NP-Completeness of Edge-Coloring
• Graph colorings with local constraints -- a survey
• Precoloring Extension III: Classes of Perfect Graphs