Decomposing Berge graphs and detecting balanced skew partitions (Q2464161)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Decomposing Berge graphs and detecting balanced skew partitions
scientific article

    Statements

    Decomposing Berge graphs and detecting balanced skew partitions (English)
    0 references
    0 references
    10 December 2007
    0 references
    A hole in a graph is an induced cycle of order at least 4. A Berge graph has no odd holes in either itself or its complement. The author shows that the problem of deciding whether a graph has a balanced skew partition is NP-hard, but gives an \(O(n^9)\)-time algorithm for the same problem restricted to Berge graphs. The algorithm is not constructive; it only certifies whether a graph has a balanced skew partition or not. It relies on a new decomposition theorem for Berge graphs, which also implies that every Berge graph can be decomposed first by using only balanced skew partitions and then by using only 2-joins.
    0 references
    perfect graph
    0 references
    Berge graph
    0 references
    2-join
    0 references
    balanced skew partition
    0 references
    decomposition
    0 references
    detection
    0 references
    recognition
    0 references

    Identifiers