The Library
3-colouring AT-free graphs in polynomial time
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 ISSN 0178-4617.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Algorithmica | ||||
Publisher: | Springer Verlag | ||||
ISSN: | 0178-4617 | ||||
Official Date: | November 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 |