A new characterization of P6-free graphs

Pim van 't Hof, Daniël Paulusma

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)

Abstract

We study -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 is -free if and only if each connected induced subgraph of 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 -free graphs for which a smallest connected dominating subgraph is a (not induced) complete bipartite graph. Our characterization of -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 -free graph in polynomial time. This enables us to solve the Hypergraph 2-Colorability problem in polynomial time for the class of hypergraphs with -free incidence graphs.
Original languageEnglish
Pages (from-to)731-740
Number of pages10
JournalDiscrete applied mathematics
Volume158
Issue number7
DOIs
Publication statusPublished - 2010
Externally publishedYes

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

Cite this