Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable

被引：5

作者：

Chudnovsky, Maria ^{[1
]}

Liu, Chun-Hung ^{[1
,7
]}

Schaudt, Oliver ^{[2
]}

Spirkl, Sophie ^{[1
,6
]}

Trotignon, Nicolas ^{[3
]}

Vuskovic, Kristina ^{[4
,5
]}

机构：

[1] Princeton Univ, Program Appl & Computat Math, Princeton, NJ 08544 USA

[2] Univ Cologne, Cologne, Germany

[3] Univ Lyon, ENS Lyon, Inst Informat, CNRS,LIP, Lyon, France

[4] Univ Leeds, Sch Comp, Leeds, W Yorkshire, England

[5] Union Univ, Fac Comp Sci, Belgrade, Serbia

[6] Rutgers State Univ, Dept Math, Hill Ctr, Busch Campus,110 Frelinghuysen Rd, Piscataway, NJ 08854 USA

[7] Texas A&M Univ, Dept Math, Mailstop 3368, College Stn, TX 77843 USA

来源：

JOURNAL OF GRAPH THEORY | 2019年 / 92卷 / 02期

基金：

英国工程与自然科学研究理事会;

关键词：

coloring; induced subgraph; CHROMATIC NUMBER;

D O I：

10.1002/jgt.22441

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K-4 are 3-colorable. This proves a conjecture of Trotignon and Vuskovic [J. Graph Theory. 84 (2017), no. 3, pp. 233-248].

引用

页码：67 / 95

页数：29

共 17 条

[1] Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures
Chudnovsky, Maria
Scott, Alex
Seymour, Paul
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 118 : 109 - 128
[2] Excluding Induced Subdivisions of the Bull and Related Graphs
Chudnovsky, Maria
Penev, Irena
Scott, Alex
Trotignon, Nicolas
[J]. JOURNAL OF GRAPH THEORY, 2012, 71 (01) : 49 - 68
[3] TOPOLOGY OF SERIES-PARALLEL NETWORKS
DUFFIN, RJ
[J]. JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1965, 10 (02) : 303 - &
[4] Gy A., 1987, P INT C COMB AN ITS, V3, P413
[5] Karthick T, 2018, GRAPH COMBINATOR, V34, P677, DOI 10.1007/s00373-018-1905-9
[6] Vizing Bound for the Chromatic Number on Some Graph Classes
Karthick, T.
Maffray, Frederic
[J]. GRAPHS AND COMBINATORICS, 2016, 32 (04) : 1447 - 1460
[7] Karthick T., ARXIV180505007
[8] Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
Kloks, Ton
Mueller, Haiko
Vuskovic, Kristina
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (05) : 733 - 800
[9] Le N. K., 2017, ELECT NOTES DISCRETE, V62, P315
[10] Chromatic Number of ISK4-Free Graphs
Le, Ngoc Khang
[J]. GRAPHS AND COMBINATORICS, 2017, 33 (06) : 1635 - 1646

← 1 2 →