Properly colored Hamilton cycles in edge-colored complete graphs

N. Alon; G. Gutin

doi:10.1002/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P

Properly colored Hamilton cycles in edge-colored complete graphs

N. Alon, G. Gutin

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

48 Scopus citations

Abstract

It is shown that, for ∈ > 0 and n > n₀(∈), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 - 1 / √2 - ∈)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors.

Original language	English (US)
Pages (from-to)	179-186
Number of pages	8
Journal	Random Structures and Algorithms
Volume	11
Issue number	2
DOIs	https://doi.org/10.1002/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P
State	Published - Sep 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Keywords

Alternating cycles
Directed graphs
Edge-colored graphs
Hamilton cycles

Access to Document

10.1002/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P

Cite this

@article{98b21bcc7ba241179a3ca0e95b109534,

title = "Properly colored Hamilton cycles in edge-colored complete graphs",

abstract = "It is shown that, for ∈ > 0 and n > n0(∈), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 - 1 / √2 - ∈)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors.",

keywords = "Alternating cycles, Directed graphs, Edge-colored graphs, Hamilton cycles",

author = "N. Alon and G. Gutin",

year = "1997",

month = sep,

doi = "10.1002/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P",

language = "English (US)",

volume = "11",

pages = "179--186",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "2",

}

TY - JOUR

T1 - Properly colored Hamilton cycles in edge-colored complete graphs

AU - Alon, N.

AU - Gutin, G.

PY - 1997/9

Y1 - 1997/9

N2 - It is shown that, for ∈ > 0 and n > n0(∈), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 - 1 / √2 - ∈)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors.

AB - It is shown that, for ∈ > 0 and n > n0(∈), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 - 1 / √2 - ∈)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors.

KW - Alternating cycles

KW - Directed graphs

KW - Edge-colored graphs

KW - Hamilton cycles

UR - http://www.scopus.com/inward/record.url?scp=0031476853&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031476853&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P

DO - 10.1002/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P

M3 - Article

AN - SCOPUS:0031476853

SN - 1042-9832

VL - 11

SP - 179

EP - 186

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 2

ER -

Properly colored Hamilton cycles in edge-colored complete graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this