On dart-free perfectly contractile graphs (extended abstract)
An even pair in a graph \(G\) is a pair of non-adjacent vertices \(x\), \(y\) such that every chordless path of \(G\) between \(x\) and \(y\) has an even number of vertices. A graph \(G\) is even contractile if it is possible to contract \(G\) to a clique through a sequence of contractions such that each contraction is applied to an even pair in the current graph. If \(G\) has the property that every induced subgraph of \(G\) is even contractile, then \(G\) is called perfectly contractile. The dart is the 5 vertex graph whose degree sequence is 4, 3, 2, 2, 1. The main result of the paper is that a recent conjecture by Everett and Reed on the forbidden structures for perfectly contractile graphs is true for graphs that are dart-free (that is, contain no induced dart). The proof implies a polynomial algorithm for recognizing dart-free perfectly contractile graphs. For the entire collection see [Zbl 0935.00049].
This page was built for publication: On dart-free perfectly contractile graphs (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508370)
