Precoloring extension on unit interval graphs

DOI10.1016/j.dam.2005.10.008zbMath1090.05028OpenAlexW1984629082MaRDI QIDQ2492199

Dániel Marx

Publication date: 9 June 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.10.008

zbMATH Keywords

NP-completeness

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Parameterized coloring problems on chordal graphs ⋮ On residual approximation in solution extension problems ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete ⋮ Flexible list colorings in graphs with special degeneracy conditions ⋮ On Residual Approximation in Solution Extension Problems ⋮ Conference Program Design with Single-Peaked and Single-Crossing Preferences ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ On coloring problems with local constraints ⋮ Minimal classes of graphs of unbounded clique-width ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Flexible List Colorings in Graphs with Special Degeneracy Conditions ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes

Cites Work

• An O(qn) algorithm to q-color a proper family of circular arcs
• Precoloring extension. I: Interval graphs
• A short proof that `proper = unit'
• Eulerian disjoint paths problem in grid graphs is NP-complete
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the disjoint paths problem
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• Precoloring Extension III: Classes of Perfect Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Precoloring extension on unit interval graphs