Hadwiger's conjecture for powers of cycles and their complements

Deming Li; Mingju Liu

doi:10.1016/j.ejc.2006.03.002

Hadwiger's conjecture for powers of cycles and their complements

Deming Li^*
, Mingju Liu

^*Corresponding author for this work

School of Mathematical Sciences

Capital Normal University

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

9 Scopus citations

Abstract

C. Thomassen showed that powers of certain cycles are counterexamples to Hajós' conjecture. We prove that powers of cycles and their complements satisfy Hadwiger's conjecture, that is, every k-chromatic graph has a k-clique as a minor.

Original language	English
Pages (from-to)	1152-1155
Number of pages	4
Journal	European Journal of Combinatorics
Volume	28
Issue number	4
DOIs	https://doi.org/10.1016/j.ejc.2006.03.002
State	Published - May 2007

Access to Document

10.1016/j.ejc.2006.03.002

Cite this

@article{1a42fa4d88604a8c9beda4ba077d1fdc,

title = "Hadwiger's conjecture for powers of cycles and their complements",

abstract = "C. Thomassen showed that powers of certain cycles are counterexamples to Haj{\'o}s' conjecture. We prove that powers of cycles and their complements satisfy Hadwiger's conjecture, that is, every k-chromatic graph has a k-clique as a minor.",

author = "Deming Li and Mingju Liu",

year = "2007",

month = may,

doi = "10.1016/j.ejc.2006.03.002",

language = "英语",

volume = "28",

pages = "1152--1155",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "4",

}

TY - JOUR

T1 - Hadwiger's conjecture for powers of cycles and their complements

AU - Li, Deming

AU - Liu, Mingju

PY - 2007/5

Y1 - 2007/5

N2 - C. Thomassen showed that powers of certain cycles are counterexamples to Hajós' conjecture. We prove that powers of cycles and their complements satisfy Hadwiger's conjecture, that is, every k-chromatic graph has a k-clique as a minor.

AB - C. Thomassen showed that powers of certain cycles are counterexamples to Hajós' conjecture. We prove that powers of cycles and their complements satisfy Hadwiger's conjecture, that is, every k-chromatic graph has a k-clique as a minor.

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

U2 - 10.1016/j.ejc.2006.03.002

DO - 10.1016/j.ejc.2006.03.002

M3 - 文章

AN - SCOPUS:33847610734

SN - 0195-6698

VL - 28

SP - 1152

EP - 1155

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 4

ER -

Hadwiger's conjecture for powers of cycles and their complements

Abstract

Access to Document

Other files and links

Fingerprint

Cite this