Coloring perfect graphs with no balanced skew-partitions

DOI10.1016/J.JCTB.2015.04.007zbMATH Open1319.05053arXiv1308.6444OpenAlexW2952375877WikidataQ57949599 ScholiaQ57949599MaRDI QIDQ490982FDOQ490982

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)

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.

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)

Cites Work

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

Cited In (4)

• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Extended formulations from communication protocols in output-efficient time
• 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)