Hof, P. van 't and Paulusma, Daniel (2010) 'A new characterization of P6-free graphs.', Discrete applied mathematics., 158 (7). pp. 731-740.
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.
|Keywords:||Paths, Cycles, Induced subgraphs, Complete bipartite graph, Dominating set, Computational complexity.|
|Full text:||PDF - Accepted Version (245Kb)|
|Publisher Web site:||http://dx.doi.org/10.1016/j.dam.2008.08.025|
|Publisher statement:||NOTICE: this is the author's version of a work that was accepted for publication in Discrete applied mathematics.|
|Record Created:||06 Oct 2010 12:35|
|Last Modified:||03 Apr 2013 13:16|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|