A new characterization of P6-free graphs
Pim van 't Hof and Daniël Paulusma
Discrete Applied Mathematics, vol. 158, no. 7, pp. 731-740, 2010.
[DOI]
[Preprint]
A preliminary version of the paper appeared in the proceedings of
COCOON 2008,
the 14th Annual International Computing and Combinatorics Conference (held on June 27-29, 2008 in Dalian, China),
Lecture Notes in Computer Science, vol. 5092,
pp. 415-424, 2008.
[DOI]
[Slides]
Abstract:
We study P6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P6-free if and only if each connected induced subgraph of G on more than one vertex contains a dominating induced cycle on six vertices or a dominating (not necessarily induced) complete bipartite subgraph. This characterization is minimal in the sense that there exists an infinite family of P6-free graphs for which a smallest connected dominating subgraph is a (not induced) complete bipartite graph. Our characterization of P6-free graphs strengthens results of Liu and Zhou, and of Liu, Peng and Zhao. Our proof has the extra advantage of being constructive: we present an algorithm that finds such a dominating subgraph of a connected P6-free graph in polynomial time. This enables us to solve the Hypergraph 2-Colorability problem in polynomial time for the class of hypergraphs with P6-free incidence graphs.