Colouring perfect graphs with bounded clique number

DOI10.1016/J.JCTB.2016.09.006MaRDI QIDQ345123zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, A. Lagoutte, Sophie Spirkl, Paul Seymour

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.03747

zbMATH Keywords

balanced skew partitioncolouring algorithmperfect graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Gr"otschel, Lov'asz, and Schrijver 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)$ of $V(G)$ such that $G[A]$ is not connected and $$ is not connected, where $$ denotes the complement graph ; and it is balanced if an additional parity condition of paths in $G$ and $$ 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$.

Recommendations

• Fast Skew Partition Recognition
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• scientific article; zbMATH DE number 3882470
• scientific article; zbMATH DE number 4202279
• scientific article; zbMATH DE number 1512686

Cites work

• About skew partitions in minimal imperfect graphs
• Berge trigraphs
• Coloring perfect graphs with no balanced skew-partitions
• Decomposing Berge graphs and detecting balanced skew partitions
• Decomposition by clique separators
• Detecting 2-joins faster
• Fast Skew Partition Recognition
• Geometric algorithms and combinatorial optimization
• On Hadwiger's Number and the Stability Number
• Some properties of minimal imperfect graphs
• Star-cutsets and perfect graphs
• The strong perfect graph theorem

Cited in

(9)

• Coloring perfect degenerate graphs
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• On the linear extension complexity of stable set polytopes for perfect graphs
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• Colouring Some Classes of Perfect Graphs Robustly
• Fast Skew Partition Recognition
• Clustered 3-colouring graphs of bounded degree
• On fork-free t-perfect graphs

This page was built for publication: Colouring perfect graphs with bounded clique number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345123)