A new characterization of P6-free graphs

Pim van 't Hof, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication14th Annual International Conference, COCOON 2008 Dalian, China, June 27-29, 2008 Proceedings
EditorsXiaodong Hu, Jie Wang
Place of PublicationBerlin, Heidelberg
Number of pages10
ISBN (Electronic)978-3-540-69733-6
ISBN (Print)978-3-540-69732-9
Publication statusPublished - 2008
Externally publishedYes
Event14th Annual International Conference on Computing and Combinatorics, COCOON 2008 - Dalian, China
Duration: 27 Jun 200829 Jun 2008
Conference number: 14

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th Annual International Conference on Computing and Combinatorics, COCOON 2008
Abbreviated titleCOCOON 2008


Dive into the research topics of 'A new characterization of P6-free graphs'. Together they form a unique fingerprint.

Cite this