Totally odd K-4-subdivisions in 4-chromatic graphs

Carsten Thomassen

doi:10.1007/s004930100006

Totally odd K-4-subdivisions in 4-chromatic graphs

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of K-4 in which each edge of K-4 corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang.

Original language	English
Journal	Combinatorica
Volume	21
Issue number	3
Pages (from-to)	217-443
ISSN	0209-9683
DOIs	https://doi.org/10.1007/s004930100006
Publication status	Published - 2001

Access to Document

10.1007/s004930100006

OpenUrl availability

Full text

Cite this

@article{62bf3f23413d4369b5791269c50f7676,

title = "Totally odd K-4-subdivisions in 4-chromatic graphs",

abstract = "We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of K-4 in which each edge of K-4 corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang. ",

author = "Carsten Thomassen",

year = "2001",

doi = "10.1007/s004930100006",

language = "English",

volume = "21",

pages = "217--443",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - Totally odd K-4-subdivisions in 4-chromatic graphs

AU - Thomassen, Carsten

PY - 2001

Y1 - 2001

N2 - We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of K-4 in which each edge of K-4 corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang.

AB - We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of K-4 in which each edge of K-4 corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang.

U2 - 10.1007/s004930100006

DO - 10.1007/s004930100006

M3 - Journal article

SN - 0209-9683

VL - 21

SP - 217

EP - 443

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

Totally odd K-4-subdivisions in 4-chromatic graphs

Abstract

Access to Document

OpenUrl availability

Fingerprint

Cite this