THE CHROMATIC NUMBER OF (P6, C4, diamond)-FREE GRAPHS

作者：Lan, Kaiyang; Zhou, Yidong; Liu, Feng^*

来源：BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2023, 108(1): 1-10.

DOI：10.1017/S0004972722001034

• chromatic number
• induced subgraph
• F-free graph

The diamond is the complete graph on four vertices minus one edge; P-n and C-n denote the path and cycle on n vertices, respectively. We prove that the chromatic number of a (P-6, C-4, diamond)-free graph G is no larger than the maximum of 3 and the clique number of G.

• 单位
  福州大学