Even pairs
An even pair in a graph consists of two nonadjacent vertices between which every induced path has an even number of edges. A graph \(G\) is even-contractile if there exists a sequence \(G = G_0, G_1, G_2, \ldots, G_j\) such that \(G_j\) is a clique, \(G_{i+1}\) is obtained from \(G_i\) by contracting an even pair of \(G_i\). A graph \(G\) is perfectly contractile if each of its induced subgraphs is even-contractile. Even pairs are related to perfect and perfectly contractile graphs form an interesting class of perfect graphs. The paper is an update version of the survey [Path parity and perfection, Discrete Math. 165/166, 223-242 (1997; Zbl 0879.05053)] by the same authors.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].
- Even pairs in Berge graphs
- Coloring Artemis graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Even and odd pairs in linegraphs of bipartite graphs
- Coloring square-free Berge graphs
- Even pairs and prism corners in square-free Berge graphs
- Finding induced paths of given parity in claw-free graphs
- A class of perfectly contractile graphs
- On the complexity of finding even pairs in planar perfect graphs
- Odd pairs of cliques
- Coloring Meyniel graphs in linear time
- Three-colourable perfect graphs without even pairs
- scientific article; zbMATH DE number 1512683 (Why is no real title available?)
- Perfectly contractile diamond-free graphs
- Ample pairs
- On Roussel-Rubio-type lemmas and their consequences
- Graph transformations preserving the stability number
- On the structure of bull-free perfect graphs
- Even pairs in Berge graphs with no balanced skew-partitions
- Precoloring extension of co-Meyniel graphs
This page was built for publication: Even pairs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2758333)
