The Chromatic Number of a Graph with Two Odd Holes and an Odd Girth

被引：0
作者：
Lan, Kaiyang [1 ]
Liu, Feng [2 ]
机构：
[1] Fuzhou Univ, Ctr Discrete Math, Fujian 350003, Peoples R China
[2] East China Normal Univ, Dept Math, Shanghai 200241, Peoples R China
来源：
GRAPHS AND COMBINATORICS | 2023年 / 39卷 / 06期
关键词：
Chromatic number; Girth; Odd hole;
D O I：
10.1007/s00373-023-02723-y
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
An odd hole is an induced odd cycle of length at least five. Let l >= 2 be an integer, and let G(l) denote the family of graphs which have girth 2l + 1 and have no holes of odd length at least 2l + 5. In this paper, we prove that every graph G is an element of U(l >= 3)G(l) is 4-colourable.
引用
收藏
页数：6
相关论文
共 10 条
  • [1] Bondy J. A., 2008, Graph Theory
  • [2] Chudnovsky M., 2023, J. Graph Theory, P1
  • [3] Di W, 2022, Arxiv, DOI arXiv:2206.01400
  • [4] A note on a conjecture of Wu, Xu and Xu
    Lan, Kaiyang
    Liu, Feng
    Zhou, Yidong
    [J]. DISCRETE APPLIED MATHEMATICS, 2023, 326 : 33 - 36
  • [5] Nelson D, 2011, ELECTRON J COMB, V18
  • [6] Plummer M., 2014, Electron. J. Combin, V21, P1, DOI [10.37236/2315, DOI 10.37236/2315]
  • [7] West D. B., 2000, Introduction to Graph Theory, V2nd
  • [8] [吴狄 Wu Di], 2023, [中国科学. 数学, Scientia Sinica Mathematica], V53, P103
  • [9] Xu B., 2017, Electron. J. Combin, V24, P4, DOI [10.37236/5555, DOI 10.37236/5555]
  • [10] On the structure of pentagraphs
    Xu, Yian
    [J]. APPLIED MATHEMATICS AND COMPUTATION, 2023, 439
1