Colouring perfect graphs with bounded clique number

DOI10.1016/j.jctb.2016.09.006zbMath1350.05030arXiv1707.03747OpenAlexW2525388293MaRDI QIDQ345123

Aurélie Lagoutte, Sophie Spirkl, Maria Chudnovsky, P. D. 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

perfect graphcolouring algorithmbalanced skew partition

Mathematics Subject Classification ID

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

Related Items (2)

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

Cites Work

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

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