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 P6-free graph in polynomial time. This enables us to solve the Hypergraph 2-Colorability problem in polynomial time for the class of hypergraphs with P6-free incidence graphs.udud
展开▼
机译：我们研究无P6图，即在六个顶点上不包含诱导路径的图。我们的主要结果是对该图类进行新的表征：当且仅当在一个以上顶点上的G的每个相连的诱导子图包含六个顶点上的主导诱导周期或一个主导（不一定是诱导）时，图G才不含P6。完整的二部图。在存在无限个不含P6的图族的情况下，此特征是最小的，对于这些图，最小的连接的支配子图是一个（未诱导的）完全二部图。我们对无P6图的表征加强了Liu和Zhou以及Liu，Peng和Zhao的结果。我们的证明具有构造性的额外优点：我们提出一种算法，可以在多项式时间内找到所连接的无P6图的这种主要子图。这使我们能够解决带有无P6入射图的超图类在多项式时间内的超图2可着色性问题。 ud ud
展开▼
