A new characterization of P6-free graphs

Pim van 't Hof; Daniël Paulusma

doi:10.1007/978-3-540-69733-6_41

A new characterization of P6-free graphs

Pim van 't Hof
, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

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.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	14th Annual International Conference, COCOON 2008 Dalian, China, June 27-29, 2008 Proceedings
Editors	Xiaodong Hu, Jie Wang
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	415-424
Number of pages	10
ISBN (Electronic)	978-3-540-69733-6
ISBN (Print)	978-3-540-69732-9
DOIs	https://doi.org/10.1007/978-3-540-69733-6_41
Publication status	Published - 2008
Externally published	Yes
Event	14th Annual International Conference on Computing and Combinatorics, COCOON 2008 - Dalian, China Duration: 27 Jun 2008 → 29 Jun 2008 Conference number: 14

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5092
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Annual International Conference on Computing and Combinatorics, COCOON 2008
Abbreviated title	COCOON 2008
Country/Territory	China
City	Dalian
Period	27/06/08 → 29/06/08

Access to Document

10.1007/978-3-540-69733-6_41

Cite this

@inproceedings{b3c0410b8c9748ff9c151280c9a22696,

title = "A new characterization of P6-free graphs",

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.",

author = "\{van 't Hof\}, Pim and Dani{\"e}l Paulusma",

year = "2008",

doi = "10.1007/978-3-540-69733-6\_41",

language = "English",

isbn = "978-3-540-69732-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "415--424",

editor = "Xiaodong Hu and Jie Wang",

booktitle = "Computing and Combinatorics",

address = "Germany",

note = "14th Annual International Conference on Computing and Combinatorics, COCOON 2008, COCOON 2008 ; Conference date: 27-06-2008 Through 29-06-2008",

}

van 't Hof, P & 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 Dalian, China, June 27-29, 2008 Proceedings. Lecture Notes in Computer Science, vol. 5092, Springer, Berlin, Heidelberg, pp. 415-424, 14th Annual International Conference on Computing and Combinatorics, COCOON 2008, Dalian, China, 27/06/08. https://doi.org/10.1007/978-3-540-69733-6_41

A new characterization of P6-free graphs. / van 't Hof, Pim; Paulusma, Daniël.
Computing and Combinatorics: 14th Annual International Conference, COCOON 2008 Dalian, China, June 27-29, 2008 Proceedings. ed. / Xiaodong Hu; Jie Wang. Berlin, Heidelberg: Springer, 2008. p. 415-424 (Lecture Notes in Computer Science; Vol. 5092).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A new characterization of P6-free graphs

AU - van 't Hof, Pim

AU - Paulusma, Daniël

N1 - Conference code: 14

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-69733-6_41

DO - 10.1007/978-3-540-69733-6_41

M3 - Conference contribution

SN - 978-3-540-69732-9

T3 - Lecture Notes in Computer Science

SP - 415

EP - 424

BT - Computing and Combinatorics

A2 - Hu, Xiaodong

A2 - Wang, Jie

PB - Springer

CY - Berlin, Heidelberg

T2 - 14th Annual International Conference on Computing and Combinatorics, COCOON 2008

Y2 - 27 June 2008 through 29 June 2008

ER -

A new characterization of P6-free graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this