A New Characterization of P6-Free Graphs
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 Pefree graph in polynomial time. This enables us to solve the Hypergraph 2-Colorability problem in polynomial time for the class of hypergraphs with P6free incidence graphs.
Pim van t Hof Daniel Paulusma
Department of Computer Science, Durham University, Science Laboratories, South Road, Durham DH1 3LE, Department of Computer Science, Durham University, Science Laboratories, South Road,Durham DH1 3LE,
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
415-424
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）