A note on color-bias Hamilton cycles in dense graphs

Andrea Freschi; Joseph Hyde; Joanna Lada; Andrew Treglown

doi:10.1137/20M1378983

A note on color-bias Hamilton cycles in dense graphs

Andrea Freschi
, Joseph Hyde
, Joanna Lada
, Andrew Treglown

Mathematics

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

297 Downloads (Pure)

Abstract

Balogh, Csaba, Jing, and Pluhár [Electron. J. Combin., 27 (2020)] recently determined the minimum degree threshold that ensures a 2-colored graph $G$ contains a Hamilton cycle of significant color bias (i.e., a Hamilton cycle that contains significantly more than half of its edges in one color). In this short note we extend this result, determining the corresponding threshold for $r$-colorings.

Original language	English
Pages (from-to)	970-975
Journal	SIAM Journal on Discrete Mathematics
Volume	35
Issue number	2
DOIs	https://doi.org/10.1137/20M1378983
Publication status	Published - 11 May 2021

Keywords

Hamilton cycles
color-bias
discrepancy

Access to Document

10.1137/20M1378983Licence: None: All rights reserved

FreschiA2021note
Freschi, A. et al., 2021. A Note on Color-Bias Hamilton Cycles in Dense Graphs. SIAM Journal on Discrete Mathematics, 35(2), pp.970–975. Available at: http://dx.doi.org/10.1137/20m1378983. © 2021 Society for Industrial and Applied Mathematics
Final published version, 310 KBLicence: None: All rights reserved

Cite this

@article{bf729fba1975463a8e9293aef13e01f2,

title = "A note on color-bias Hamilton cycles in dense graphs",

abstract = "Balogh, Csaba, Jing, and Pluh{\'a}r [Electron. J. Combin., 27 (2020)] recently determined the minimum degree threshold that ensures a 2-colored graph \$G\$ contains a Hamilton cycle of significant color bias (i.e., a Hamilton cycle that contains significantly more than half of its edges in one color). In this short note we extend this result, determining the corresponding threshold for \$r\$-colorings.",

keywords = "Hamilton cycles, color-bias, discrepancy",

author = "Andrea Freschi and Joseph Hyde and Joanna Lada and Andrew Treglown",

year = "2021",

month = may,

day = "11",

doi = "10.1137/20M1378983",

language = "English",

volume = "35",

pages = "970--975",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

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

number = "2",

}

TY - JOUR

T1 - A note on color-bias Hamilton cycles in dense graphs

AU - Freschi, Andrea

AU - Hyde, Joseph

AU - Lada, Joanna

AU - Treglown, Andrew

PY - 2021/5/11

Y1 - 2021/5/11

N2 - Balogh, Csaba, Jing, and Pluhár [Electron. J. Combin., 27 (2020)] recently determined the minimum degree threshold that ensures a 2-colored graph $G$ contains a Hamilton cycle of significant color bias (i.e., a Hamilton cycle that contains significantly more than half of its edges in one color). In this short note we extend this result, determining the corresponding threshold for $r$-colorings.

AB - Balogh, Csaba, Jing, and Pluhár [Electron. J. Combin., 27 (2020)] recently determined the minimum degree threshold that ensures a 2-colored graph $G$ contains a Hamilton cycle of significant color bias (i.e., a Hamilton cycle that contains significantly more than half of its edges in one color). In this short note we extend this result, determining the corresponding threshold for $r$-colorings.

KW - Hamilton cycles

KW - color-bias

KW - discrepancy

UR - https://arxiv.org/abs/2011.03948

U2 - 10.1137/20M1378983

DO - 10.1137/20M1378983

M3 - Article

SN - 0895-4801

VL - 35

SP - 970

EP - 975

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

A note on color-bias Hamilton cycles in dense graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this