NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

DOI10.1002/jgt.20085zbMath1068.05024OpenAlexW4245621972MaRDI QIDQ5311921

Dániel Marx

Publication date: 29 August 2005

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20085

zbMATH Keywords

edge coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

List-edge-colouring planar graphs with precoloured edges ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Extending partial representations of interval graphs ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ Invited talks ⋮ Decomposition of university course timetabling. A systematic study of subproblems and their complexities ⋮ Complexity results for minimum sum edge coloring ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Mixed graph edge coloring

Cites Work

• Complexity results for minimum sum edge coloring
• Graph colorings with local constraints -- a survey
• Edge-Coloring and f-Coloring for Various Classes of Graphs
• Algorithms and Computation
• Hard tiling problems with simple tiles
• Unnamed Item

This page was built for publication: NP‐completeness of list coloring and precoloring extension on the edges of planar graphs