Precoloring extension on unit interval graphs
From MaRDI portal
Publication:2492199
DOI10.1016/j.dam.2005.10.008zbMath1090.05028MaRDI QIDQ2492199
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
Related Items
Exploring the complexity boundary between coloring and list-coloring, Parameterized coloring problems on chordal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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