The chromatic number of { ISK 4, diamond, bowtie}-free graphs
The chromatic number of { ISK 4, diamond, bowtie}-free graphs
复制标题
{ISK 4, Diamond, Bowtie}-free 图的色数
DOI：
10.1002/jgt.22631
复制
发表时间：
2021
影响因子：
0.9
通讯作者：
Liu Qinghai
中科院分区：
文献类型：
--
作者：
Chen Guantao;Chen Yuan;Cui Qing;Feng Xing;Liu Qinghai
如果一个图不包含诱导子图的任何细分，我们就说它是自由的。Lévêque， Maffray和Trotignon推测每个自由图都是4色的。在本文中，我们证明了这个猜想对于{，菱形，领结}- free图是成立的，其中菱形是去掉一条边得到的图，领结是由两个三角形组成的图，其中一个顶点被识别出来。
A graph is said to be‐free if it does not contain any subdivision ofas an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of {, diamond, bowtie}‐free graphs, where a diamond is the graph obtained fromby removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified.