## 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 *P*_{6}-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 *P*_{6}-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 *P*_{6}-free graphs for which a smallest connected dominating subgraph
is a (not induced) complete bipartite graph.
Our characterization of *P*_{6}-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 *P*_{6}-free graph in polynomial time.
This enables us to solve the
Hypergraph 2-Colorability
problem in polynomial time for the class of hypergraphs
with *P*_{6}-free incidence graphs.