Duchet-type theorems for powers of HHD-free graphs (Q1377865)

The \(k\)th power of a graph \(G\), denoted \(G^k\), is the graph with the vertex set \(V(G)\) in which two vertices are adjacent if their distance in \(G\) is at most \(k\). The authors prove three results of ``Duchet-type''; that is, results which read: ``If \(G^k\) contains no induced subgraph of a certain type (say, long cycles), then so does \(G^{k+2}\).'' They do so by employing an idea of Duchet: One can define a new graph \((G^k)(X)\), with vertices certain subsets of \(V(G)\), that is isomorphic to \(G^{k+2}\), and work out the results in \((G^k)(X)\).