K                         5                          -subdivision in 4-connected graphs

Changhong Lu; Ping Zhang

doi:10.1137/18M1194973

K ₅ -subdivision in 4-connected graphs

Changhong Lu, Ping Zhang

School of Mathematical Sciences

East China Normal University

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

Abstract

Hajos conjectured in 1961 that every k-chromatic graph contains a K _k -subdivision. In this paper, we consider the subdivision of K ^- ₅ and prove that every 4-connected graph contains a K ₅ -subdivision. This may make progress for the case k = 5 of the Hajós' conjecture.

Original language	English
Pages (from-to)	2900-2915
Number of pages	16
Journal	SIAM Journal on Discrete Mathematics
Volume	32
Issue number	4
DOIs	https://doi.org/10.1137/18M1194973
State	Published - Jan 2018

Keywords

Connectivity
Contraction
Internally disjoint paths
K -subdivision

Access to Document

10.1137/18M1194973

Cite this

@article{55f8aa893f8d4cf3b63b366f65505a6f,

title = " K 5 -subdivision in 4-connected graphs ",

abstract = " Hajos conjectured in 1961 that every k-chromatic graph contains a K k -subdivision. In this paper, we consider the subdivision of K - 5 and prove that every 4-connected graph contains a K 5 -subdivision. This may make progress for the case k = 5 of the Haj{\'o}s' conjecture.",

keywords = "Connectivity, Contraction, Internally disjoint paths, K -subdivision",

author = "Changhong Lu and Ping Zhang",

note = "Publisher Copyright: {\textcopyright} 2018 Societ y for Industrial and Applied Mathematics.",

year = "2018",

month = jan,

doi = "10.1137/18M1194973",

language = "英语",

volume = "32",

pages = "2900--2915",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - K 5 -subdivision in 4-connected graphs

AU - Lu, Changhong

AU - Zhang, Ping

PY - 2018/1

Y1 - 2018/1

N2 - Hajos conjectured in 1961 that every k-chromatic graph contains a K k -subdivision. In this paper, we consider the subdivision of K - 5 and prove that every 4-connected graph contains a K 5 -subdivision. This may make progress for the case k = 5 of the Hajós' conjecture.

AB - Hajos conjectured in 1961 that every k-chromatic graph contains a K k -subdivision. In this paper, we consider the subdivision of K - 5 and prove that every 4-connected graph contains a K 5 -subdivision. This may make progress for the case k = 5 of the Hajós' conjecture.

KW - Connectivity

KW - Contraction

KW - Internally disjoint paths

KW - K -subdivision

UR - https://www.scopus.com/pages/publications/85060033132

U2 - 10.1137/18M1194973

DO - 10.1137/18M1194973

M3 - 文章

AN - SCOPUS:85060033132

SN - 0895-4801

VL - 32

SP - 2900

EP - 2915

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -

K ₅ -subdivision in 4-connected graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this