Coloring perfect graphs with no balanced skew-partitions

DOI10.1016/J.JCTB.2015.04.007MaRDI QIDQ490982zbMATH OpenOpenAlexWikidataFDO

Authors Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck, Kristina Vušković

Publication date 21 August 2015

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

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

zbMATH Keywords

2-joinmaximum stable setperfect graphsBerge graphshomogeneous pairskew partition

Mathematics Subject Classification ID

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

Abstract: We present an $O(n^5)$ algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present $O(n^7)$ time algorithm that colors them.

Cites work

• scientific article; zbMATH DE number 1033812 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Algorithms for some \(H\)-join decompositions
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• An algorithm for finding homogeneous pairs
• Berge trigraphs
• Combinatorial optimization with 2-joins
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Decomposing Berge graphs and detecting balanced skew partitions
• Detecting 2-joins faster
• Forbidden induced subgraphs of double-split graphs
• Geometric algorithms and combinatorial optimization
• How the proof of the strong perfect graph conjecture was found
• Normal hypergraphs and the perfect graph conjecture
• Recognizing Berge graphs
• The splittance of a graph
• The strong perfect graph theorem

Cited in

(3)

• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Colouring perfect graphs with bounded clique number
• On the linear extension complexity of stable set polytopes for perfect graphs

This page was built for publication: Coloring perfect graphs with no balanced skew-partitions

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