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.64 (No.3). pp. 384-399. doi:10.1007/s00453-012-9624-8
Research output not available from this repository, contact author.
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 | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Volume: | Vol.64 | ||||
| Number: | No.3 | ||||
| Page Range: | pp. 384-399 | ||||
| DOI: | 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" |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
