Cycle extension in edge-colored complete graphs

Ruonan Li, Haitze J. Broersma, Chuandong Xu, Shenggui Zhang

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily properly) edge-colored complete graphs. Fujita and Magnant (2011) conjectured that in an edge-colored complete graph on n vertices with minimum color degree at least (n+1)∕2, each vertex is contained in a properly edge-colored cycle of length k, for all k with 3≤k≤n. They confirmed the conjecture for k=3 and k=4, and they showed that each vertex is contained in a properly edge-colored cycle of length at least 5 when n≥13, but even the existence of properly edge-colored Hamilton cycles is unknown (in complete graphs that satisfy the conditions of the conjecture). We prove a cycle extension result that implies that each vertex is contained in a properly edge-colored cycle of length at least the minimum color degree.
Original languageEnglish
Pages (from-to)1235-1241
JournalDiscrete mathematics
Volume340
Issue number6
DOIs
Publication statusPublished - Jun 2017

Keywords

  • Edge-colored graph
  • Complete graph
  • Properly colored cycle

Cite this

Li, Ruonan ; Broersma, Haitze J. ; Xu, Chuandong ; Zhang, Shenggui. / Cycle extension in edge-colored complete graphs. In: Discrete mathematics. 2017 ; Vol. 340, No. 6. pp. 1235-1241.
@article{635b1a1653a14350bcf22807e8bee31f,
title = "Cycle extension in edge-colored complete graphs",
abstract = "Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily properly) edge-colored complete graphs. Fujita and Magnant (2011) conjectured that in an edge-colored complete graph on n vertices with minimum color degree at least (n+1)∕2, each vertex is contained in a properly edge-colored cycle of length k, for all k with 3≤k≤n. They confirmed the conjecture for k=3 and k=4, and they showed that each vertex is contained in a properly edge-colored cycle of length at least 5 when n≥13, but even the existence of properly edge-colored Hamilton cycles is unknown (in complete graphs that satisfy the conditions of the conjecture). We prove a cycle extension result that implies that each vertex is contained in a properly edge-colored cycle of length at least the minimum color degree.",
keywords = "Edge-colored graph, Complete graph, Properly colored cycle",
author = "Ruonan Li and Broersma, {Haitze J.} and Chuandong Xu and Shenggui Zhang",
year = "2017",
month = "6",
doi = "10.1016/j.disc.2017.01.023",
language = "English",
volume = "340",
pages = "1235--1241",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "6",

}

Cycle extension in edge-colored complete graphs. / Li, Ruonan; Broersma, Haitze J.; Xu, Chuandong; Zhang, Shenggui.

In: Discrete mathematics, Vol. 340, No. 6, 06.2017, p. 1235-1241.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Cycle extension in edge-colored complete graphs

AU - Li, Ruonan

AU - Broersma, Haitze J.

AU - Xu, Chuandong

AU - Zhang, Shenggui

PY - 2017/6

Y1 - 2017/6

N2 - Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily properly) edge-colored complete graphs. Fujita and Magnant (2011) conjectured that in an edge-colored complete graph on n vertices with minimum color degree at least (n+1)∕2, each vertex is contained in a properly edge-colored cycle of length k, for all k with 3≤k≤n. They confirmed the conjecture for k=3 and k=4, and they showed that each vertex is contained in a properly edge-colored cycle of length at least 5 when n≥13, but even the existence of properly edge-colored Hamilton cycles is unknown (in complete graphs that satisfy the conditions of the conjecture). We prove a cycle extension result that implies that each vertex is contained in a properly edge-colored cycle of length at least the minimum color degree.

AB - Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily properly) edge-colored complete graphs. Fujita and Magnant (2011) conjectured that in an edge-colored complete graph on n vertices with minimum color degree at least (n+1)∕2, each vertex is contained in a properly edge-colored cycle of length k, for all k with 3≤k≤n. They confirmed the conjecture for k=3 and k=4, and they showed that each vertex is contained in a properly edge-colored cycle of length at least 5 when n≥13, but even the existence of properly edge-colored Hamilton cycles is unknown (in complete graphs that satisfy the conditions of the conjecture). We prove a cycle extension result that implies that each vertex is contained in a properly edge-colored cycle of length at least the minimum color degree.

KW - Edge-colored graph

KW - Complete graph

KW - Properly colored cycle

U2 - 10.1016/j.disc.2017.01.023

DO - 10.1016/j.disc.2017.01.023

M3 - Article

VL - 340

SP - 1235

EP - 1241

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 6

ER -