Skip to main content

Research Repository

Advanced Search

A new characterization of P6-free graphs

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

Authors

P. van't Hof



Contributors

Xiaodong Hu
Editor

Jie Wang
Editor

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.

Citation

Hof, P. V., & Paulusma, D. (2008). A new characterization of P6-free graphs. In X. Hu, & J. Wang (Eds.), Computing and combinatorics, 14th Annual International Conference, COCOON 2008, 27-29 June 2008 Dalian, China ; proceedings (415-424). https://doi.org/10.1007/978-3-540-69733-6_41

Conference Name 14th Annual International Computing and Combinatorics Conference
Conference Location Dalian, China
Publication Date Jun 1, 2008
Deposit Date Oct 6, 2010
Pages 415-424
Series Title Lecture notes in computer science
Series Number 5092
Series ISSN 0302-9743,1611-3349
Edition 14th ed.
Book Title Computing and combinatorics, 14th Annual International Conference, COCOON 2008, 27-29 June 2008 Dalian, China ; proceedings.
DOI https://doi.org/10.1007/978-3-540-69733-6_41
Public URL https://durham-repository.worktribe.com/output/1159279


You might also like



Downloadable Citations