Name
Abstract | ||
|---|---|---|
Each fixed graph H gives rise to a list H-colouring problem. The complexity of list H-colouring problems has recently been fully classified: if H is a bi-arc graph, the problem is polynomial-time solvable, and otherwise it is NP-complete. The proof of this fact relies on a forbidden substructure characterization of bi-arc graphs, reminiscent of the theorem of Lekkerkerker and Boland on interval graphs. In this note we show that in fact the theorem of Lekkerkerker and Boland can be derived from the characterization. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.disc.2004.02.022 | Discrete Mathematics |
Keywords | Field | DocType |
vertex-asteroids,bi-arc graphs,polynomial algorithms,np-completeness,np -completeness,interval graph,list h -colouring,edge-asteroid,asteroidal triples,list h-colouring,polynomial time,np completeness | Discrete mathematics,Graph,NP-complete,Combinatorics,Interval graph,Forbidden graph characterization,Polynomial algorithm,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
299 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pavol Hell | 1 | 2638 | 288.75 |
| Jing Huang | 2 | 2464 | 186.09 |