The Chromatic Number of Graphs with No Induced Subdivision of K4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_4$$\end{document}

被引：0
作者：
Guantao Chen
Yuan Chen
Qing Cui
Xing Feng
Qinghai Liu
机构：
[1] Georgia State University,Department of Mathematics and Statistics
[2] Wuhan Textile University,Research Center of Nonlinear Science, School of Mathematics and Computer Science
[3] Nanjing University of Aeronautics and Astronautics,Department of Mathematics
[4] Jiangxi University of Science and Technology,Faculty of Science
[5] Fuzhou University,Center for Discrete Mathematics
来源：
Graphs and Combinatorics | 2020年 / 36卷 / 3期
关键词：
Chromatic number; Subdivision; ISK4; 05C15; 05C12;
D O I：
10.1007/s00373-020-02148-x
中图分类号：
学科分类号：
摘要：
In 2012, Lévêque, Maffray and Trotignon conjectured that if a graph does not contain an induced subdivision of K4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_4$$\end{document}, then it is 4-colorable. Recently, Le showed that every such graph is 24-colorable. In this paper, we improve the upper bound to 8.
引用
收藏
页码：719 / 728
页数：9
相关论文
共 23 条
[1]  
Chudnovsky M(2019)Triangle-free graphs that do not contain an induced subdivision of J. Graph Theroy 92 67-95
[2]  
Liu C-H(1987) are 3-colorable Zastow Mat. Appl. Math. 19 413-441
[3]  
Schaudt O(2004)Problems from the world surrounding perfect graphs Combinatorica 24 287-304
[4]  
Spirkl S(2017)Induced subdivisions in Graphs Comb. 33 1635-1646
[5]  
Trotignon N(2012)-free graphs of large average degree J. Comb. Theory Ser. B 102 924-947
[6]  
Vušković K(2014)Chromatic number of ISK4-free graphs J. Comb. Theory Ser. B 105 6-10
[7]  
Gyárfás A(1997)On graphs with no induced subdivision of J. Graph Theroy 24 297-311
[8]  
Kühn D(2017)Triangle-free intersection graphs of line segments with large chromatic number J. Graph Theroy 84 233-248
[9]  
Osthus D(undefined)Induced trees in graphs of large chromatic number undefined undefined undefined-undefined
[10]  
Le NK(undefined)On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph undefined undefined undefined-undefined
123