A new characterization of P6-free graphs

Hof, P. van 't; Paulusma, D.

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.

Citation

Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025

• Journal Article Type: Article
• Publication Date: Apr 6, 2010
• Deposit Date: Oct 6, 2010
• Publicly Available Date: Oct 7, 2010
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 158
• Issue: 7
• Pages: 731-740
• DOI: https://doi.org/10.1016/j.dam.2008.08.025
• Keywords: Paths, Cycles, Induced subgraphs, Complete bipartite graph, Dominating set, Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1517209