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

被引:0
作者
Kaiyang Lan
Feng Liu
机构
[1] Fuzhou University,Center for Discrete Mathematics
[2] East China Normal University,Department of Mathematics
来源
Graphs and Combinatorics | 2023年 / 39卷
关键词
Chromatic number; Girth; Odd hole; 05C15; 05C38; 05C60;
D O I
暂无
中图分类号
学科分类号
摘要
An odd hole is an induced odd cycle of length at least five. Let ℓ≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell \ge 2$$\end{document} be an integer, and let Gℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {G}}_\ell $$\end{document} denote the family of graphs which have girth 2ℓ+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\ell + 1$$\end{document} and have no holes of odd length at least 2ℓ+5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\ell +5$$\end{document}. In this paper, we prove that every graph G∈∪ℓ≥3Gℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G \in \cup _{\ell \ge 3}{\mathcal {G}}_\ell $$\end{document} is 4-colourable.
引用
收藏
相关论文
共 16 条
  • [1] Lan K(2023)A note on a conjecture of Wu, Xu and Xu Discret. Appl. Math. 326 33-36
  • [2] Liu F(2011)On a conjecture concerning the Petersen graph Electron. J. Combin. 18 20-34
  • [3] Zhou Y(2014)On a conjecture concerning the Petersen graph: part II Electron. J. Combin. 21 1-120
  • [4] Nelson D(2023)On coloring of graphs of girth Sci. China Math. 53 103-32
  • [5] Plummer M(2017) without longer odd holes (in Chinese) Electron. J. Combin. 24 4-undefined
  • [6] Robertson N(2023)A note on chromatic number and induced odd cycles Appl. Math. Comput. 439 127632-undefined
  • [7] Zha X(undefined)On the structure of pentagraphs undefined undefined undefined-undefined
  • [8] Plummer M(undefined)undefined undefined undefined undefined-undefined
  • [9] Zha X(undefined)undefined undefined undefined undefined-undefined
  • [10] Wu D(undefined)undefined undefined undefined undefined-undefined