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

Maria Chudnovsky; Chun Hung Liu; Oliver Schaudt; Sophie Spirkl; Nicolas Trotignon; Kristina Vušković

doi:10.1002/jgt.22441

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

Maria Chudnovsky, Chun Hung Liu, Oliver Schaudt, Sophie Spirkl, Nicolas Trotignon, Kristina Vušković

Mathematics

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	67-95
Number of pages	29
Journal	Journal of Graph Theory
Volume	92
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22441
State	Published - Oct 2019

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

coloring
induced subgraph

Access to Document

10.1002/jgt.22441

Cite this

@article{a265b666b4904240b8aedfde67f1241a,

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

abstract = "We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vu{\v s}kovi{\'c} [J. Graph Theory. 84 (2017), no. 3, pp. 233–248].",

keywords = "coloring, induced subgraph",

author = "Maria Chudnovsky and Liu, {Chun Hung} and Oliver Schaudt and Sophie Spirkl and Nicolas Trotignon and Kristina Vu{\v s}kovi{\'c}",

note = "Publisher Copyright: {\textcopyright} 2018 Wiley Periodicals, Inc.",

year = "2019",

month = oct,

doi = "10.1002/jgt.22441",

language = "English (US)",

volume = "92",

pages = "67--95",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

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

AU - Chudnovsky, Maria

AU - Liu, Chun Hung

AU - Schaudt, Oliver

AU - Spirkl, Sophie

AU - Trotignon, Nicolas

AU - Vušković, Kristina

PY - 2019/10

Y1 - 2019/10

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

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

KW - coloring

KW - induced subgraph

UR - http://www.scopus.com/inward/record.url?scp=85058402421&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85058402421&partnerID=8YFLogxK

U2 - 10.1002/jgt.22441

DO - 10.1002/jgt.22441

M3 - Article

AN - SCOPUS:85058402421

SN - 0364-9024

VL - 92

SP - 67

EP - 95

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -