Hajós' conjecture and cycle power graphs

Deming Li; Mingju Liu; Yumei Peng

doi:10.1016/j.ejc.2009.08.008

Hajós' conjecture and cycle power graphs

Deming Li^*
, Mingju Liu
, Yumei Peng

^*Corresponding author for this work

School of Mathematical Sciences

Capital Normal University

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

1 Scopus citations

Abstract

Hajós' conjecture says that every graph of chromatic number k contains a subdivision of the complete graph with k vertices. In this note, we give a characterization for cycle power graphs C_n^k on Hajós' conjecture, which generalized a recent result of Thomassen (2005) [C. Thomassen, Some remarks on Hajós' conjecture, J. Combin. Theory Ser. B 93 (2005) 95105]. Precisely, we showed that for positive integers n, k such that n > 2 k + 1, and then n = q (k + 1) + r, where 0 ≤ r ≤ k, the kth power of the cycle C_n, C_n^k, satisfies Hajós' conjecture if and only if 1 + 2 + ⋯ + ⌈ r / q ⌉ ≤ k.

Original language	English
Pages (from-to)	759-764
Number of pages	6
Journal	European Journal of Combinatorics
Volume	31
Issue number	3
DOIs	https://doi.org/10.1016/j.ejc.2009.08.008
State	Published - Apr 2010

Access to Document

10.1016/j.ejc.2009.08.008

Cite this

@article{ebf29d7c9bd545a8872ad51b96ca9d81,

title = "Haj{\'o}s' conjecture and cycle power graphs",

abstract = "Haj{\'o}s' conjecture says that every graph of chromatic number k contains a subdivision of the complete graph with k vertices. In this note, we give a characterization for cycle power graphs Cnk on Haj{\'o}s' conjecture, which generalized a recent result of Thomassen (2005) [C. Thomassen, Some remarks on Haj{\'o}s' conjecture, J. Combin. Theory Ser. B 93 (2005) 95105]. Precisely, we showed that for positive integers n, k such that n > 2 k + 1, and then n = q (k + 1) + r, where 0 ≤ r ≤ k, the kth power of the cycle Cn, Cnk, satisfies Haj{\'o}s' conjecture if and only if 1 + 2 + ⋯ + ⌈ r / q ⌉ ≤ k.",

author = "Deming Li and Mingju Liu and Yumei Peng",

year = "2010",

month = apr,

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

language = "英语",

volume = "31",

pages = "759--764",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "3",

}

TY - JOUR

T1 - Hajós' conjecture and cycle power graphs

AU - Li, Deming

AU - Liu, Mingju

AU - Peng, Yumei

PY - 2010/4

Y1 - 2010/4

N2 - Hajós' conjecture says that every graph of chromatic number k contains a subdivision of the complete graph with k vertices. In this note, we give a characterization for cycle power graphs Cnk on Hajós' conjecture, which generalized a recent result of Thomassen (2005) [C. Thomassen, Some remarks on Hajós' conjecture, J. Combin. Theory Ser. B 93 (2005) 95105]. Precisely, we showed that for positive integers n, k such that n > 2 k + 1, and then n = q (k + 1) + r, where 0 ≤ r ≤ k, the kth power of the cycle Cn, Cnk, satisfies Hajós' conjecture if and only if 1 + 2 + ⋯ + ⌈ r / q ⌉ ≤ k.

AB - Hajós' conjecture says that every graph of chromatic number k contains a subdivision of the complete graph with k vertices. In this note, we give a characterization for cycle power graphs Cnk on Hajós' conjecture, which generalized a recent result of Thomassen (2005) [C. Thomassen, Some remarks on Hajós' conjecture, J. Combin. Theory Ser. B 93 (2005) 95105]. Precisely, we showed that for positive integers n, k such that n > 2 k + 1, and then n = q (k + 1) + r, where 0 ≤ r ≤ k, the kth power of the cycle Cn, Cnk, satisfies Hajós' conjecture if and only if 1 + 2 + ⋯ + ⌈ r / q ⌉ ≤ k.

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

U2 - 10.1016/j.ejc.2009.08.008

DO - 10.1016/j.ejc.2009.08.008

M3 - 文章

AN - SCOPUS:75149148569

SN - 0195-6698

VL - 31

SP - 759

EP - 764

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 3

ER -

Hajós' conjecture and cycle power graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this