Coloring perfect graphs with no balanced skew-partitions

DOI10.1016/j.jctb.2015.04.007zbMath1319.05053arXiv1308.6444OpenAlexW2952375877WikidataQ57949599 ScholiaQ57949599MaRDI QIDQ490982

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

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

skew partitionperfect graphs2-joinmaximum stable setBerge graphshomogeneous pair

Mathematics Subject Classification ID

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

Related Items (4)

Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ Colouring perfect graphs with bounded clique number ⋮ Extended formulations from communication protocols in output-efficient time ⋮ On the linear extension complexity of stable set polytopes for perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• An algorithm for finding homogeneous pairs
• Combinatorial optimization with 2-joins
• The strong perfect graph theorem
• The splittance of a graph
• Geometric algorithms and combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Detecting 2-joins faster
• Decomposing Berge graphs and detecting balanced skew partitions
• Recognizing Berge graphs
• Normal hypergraphs and the perfect graph conjecture
• Algorithms for Some H-Join Decompositions
• Forbidden Induced Subgraphs of Double-split Graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Berge trigraphs

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