Colouring perfect graphs with bounded clique number

详细信息    查看全文

• 作者：Maria Chudnovsky^a ; ¹ ; Auré ; lie Lagoutte^b ; ² ; Paul Seymour^a ; ³ ; ^{pds@math.princeton.edu} ; Sophie Spirkl^a
• 关键词：Colouring algorithm ; Perfect graph ; Balanced skew partition
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：757-775
• 全文大小：432 K
• 卷排序：122

文摘

A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Grötschel, Lovász, and Schrijver [9] from 1988 finds an optimal colouring of a perfect graph in polynomial time. But this algorithm uses the ellipsoid method, and it is a well-known open question to construct a “combinatorial” polynomial-time algorithm that yields an optimal colouring of a perfect graph.A skew partition in G   is a partition (A,B)(A,B) of V(G)V(G) such that G[A]G[A] is not connected and G‾[B] is not connected, where G‾ denotes the complement graph; and it is balanced if an additional parity condition on certain paths in G   and G‾ is satisfied.In this paper we first give a polynomial-time algorithm that, with input a perfect graph, outputs a balanced skew partition if there is one. Then we use this to obtain a combinatorial algorithm that finds an optimal colouring of a perfect graph with clique number k, in time that is polynomial for fixed k.