The Library
3-colouring AT-free graphs in polynomial time
Tools
Tools
Tools
Stacho, Juraj (2012) 3-colouring AT-free graphs in polynomial time. Algorithmica, Vol.63 (No.3). pp. 384-399. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-012-9624-8
Abstract
Determining the complexity of the colouring problem on AT-free graphs is one of long-standing open problems in algorithmic graph theory. One of the reasons behind this is that AT-free graphs are not necessarily perfect unlike many popular subclasses of AT-free graphs such as interval graphs or co-comparability graphs. In this paper, we resolve the smallest open case of this problem, and present the first polynomial time algorithm for the 3-colouring problem on AT-free graphs. © 2012 Springer Science+Business Media, LLC.
| Item Type: | Submitted Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Mathematics |
| Journal or Publication Title: | Algorithmica |
| Publisher: | Springer Verlag |
| ISSN: | 0178-4617 |
| Date: | 2012 |
| Volume: | Vol.63 |
| Number: | No.3 |
| Page Range: | pp. 384-399 |
| Identification Number: | 10.1007/s00453-012-9624-8 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Description: | From the issue entitled "Special Issue : Algorithms and Computation" |
| URI: | http://wrap.warwick.ac.uk/id/eprint/45010 |
Actions (login required)
 |
View Item |
