3-colouring AT-free graphs in polynomial time
Stacho, Juraj (2012) 3-colouring AT-free graphs in polynomial time. Algorithmica, Vol.63 (No.3). pp. 384-399. ISSN 0178-4617Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-012-9624-8
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|
|Page Range:||pp. 384-399|
|Access rights to Published version:||Restricted or Subscription Access|
|Description:||From the issue entitled "Special Issue : Algorithms and Computation"|
Actions (login required)