标题： 关于没有四顶点导出子图的图 显示英文标题

标题： On graphs without four-vertex induced subgraphs

摘要： 给定一个图族 F，如果图 G 不包含 F 中的任何图作为诱导子图，则称 G 是 F-自由图。 确定 (爪图, 4K1)-自由图的着色复杂性是一个著名的未解决问题。 本文解决了 (爪图, 4K1)-自由图的一个子类的着色问题。 我们设计了一个多项式时间算法来对 (爪图, 4K1, 桥, C4-孪生)-自由图进行着色。 该算法源自于 (爪图, 4K1, 桥, C4-孪生)-自由图的结构定理。 显示英文摘要

摘要： Given a family F of graphs, a graph G is F-free if it does not contain any graph in F as an induced subgraph. The problem of determining the complexity of colouring (claw, 4K1)- free graphs is a well-known open problem. In this paper we solve the colouring problem for a subclass of (claw, 4K1)-free graphs. We design a polynomial-time algorithm to colour (claw, 4K1, bridge, C4-twin)-free graphs. This algorithm is derived from a structural theorem on (claw, 4K1, bridge, C4-twin)-free graphs.