Edge-colored complete graphs without properly colored even cycles: A full characterization

Ruonan Li; Hajo Broersma; Maho Yokota; Kiyoshi Yoshimoto

doi:10.1002/jgt.22684

Edge-colored complete graphs without properly colored even cycles: A full characterization

Ruonan Li
, Hajo Broersma^*
, Maho Yokota
, Kiyoshi Yoshimoto

^*Corresponding author for this work

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

2 Citations (Scopus)

295 Downloads (Pure)

Abstract

The structure of edge-colored complete graphs containing no properly colored triangles has been characterized by Gallai back in the 1960s. More recently, Cǎda et al. and Fujita et al. independently determined the structure of edge-colored complete bipartite graphs containing no properly colored (Formula presented.). We characterize the structure of edge-colored complete graphs containing no properly colored even cycles, or equivalently, without a properly colored (Formula presented.) or (Formula presented.). In particular, we first deal with the simple case of 2-edge-colored complete graphs, using a result of Yeo. Next, for (Formula presented.), we define four classes of (Formula presented.) -edge-colored complete graphs without properly colored even cycles and prove that any (Formula presented.) -edge-colored complete graph without a properly colored even cycle belongs to one of these four classes.

Original language	English
Pages (from-to)	110-124
Number of pages	15
Journal	Journal of graph theory
Volume	98
Issue number	1
DOIs	https://doi.org/10.1002/jgt.22684
Publication status	Published - Sept 2021

Keywords

complete graph
edge-colored graph
forbidden subgraph
properly colored cycle
UT-Hybrid-D

Access to Document

10.1002/jgt.22684Licence: CC BY-NC-ND

Li-2021-Edgecolored-complete-graphs-withoutFinal published version, 650 KBLicence: CC BY-NC-ND

Cite this

@article{7d789daf28bc421eb6e720d1f4cb1120,

title = "Edge-colored complete graphs without properly colored even cycles: A full characterization",

abstract = "The structure of edge-colored complete graphs containing no properly colored triangles has been characterized by Gallai back in the 1960s. More recently, Cǎda et al. and Fujita et al. independently determined the structure of edge-colored complete bipartite graphs containing no properly colored (Formula presented.). We characterize the structure of edge-colored complete graphs containing no properly colored even cycles, or equivalently, without a properly colored (Formula presented.) or (Formula presented.). In particular, we first deal with the simple case of 2-edge-colored complete graphs, using a result of Yeo. Next, for (Formula presented.), we define four classes of (Formula presented.) -edge-colored complete graphs without properly colored even cycles and prove that any (Formula presented.) -edge-colored complete graph without a properly colored even cycle belongs to one of these four classes.",

keywords = "complete graph, edge-colored graph, forbidden subgraph, properly colored cycle, UT-Hybrid-D",

author = "Ruonan Li and Hajo Broersma and Maho Yokota and Kiyoshi Yoshimoto",

note = "Funding Information: We thank the two referees for carefully reading earlier versions of the manuscript, and for their useful comments that helped improving the presentation. This study was supported by NSFC (No. 11901459), Natural Science Foundation of Shaanxi Province (No. 2020JQ‐111), and the Fundamental Research Funds for the Central Universities (No. 31020180QD124). This study was also supported by JSPS. KAKENHI (No. 18K03402). Publisher Copyright: {\textcopyright} 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.",

year = "2021",

month = sep,

doi = "10.1002/jgt.22684",

language = "English",

volume = "98",

pages = "110--124",

journal = "Journal of graph theory",

issn = "0364-9024",

publisher = "Wiley",

number = "1",

}

TY - JOUR

T1 - Edge-colored complete graphs without properly colored even cycles

T2 - A full characterization

AU - Li, Ruonan

AU - Broersma, Hajo

AU - Yokota, Maho

AU - Yoshimoto, Kiyoshi

N1 - Funding Information: We thank the two referees for carefully reading earlier versions of the manuscript, and for their useful comments that helped improving the presentation. This study was supported by NSFC (No. 11901459), Natural Science Foundation of Shaanxi Province (No. 2020JQ‐111), and the Fundamental Research Funds for the Central Universities (No. 31020180QD124). This study was also supported by JSPS. KAKENHI (No. 18K03402). Publisher Copyright: © 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.

PY - 2021/9

Y1 - 2021/9

N2 - The structure of edge-colored complete graphs containing no properly colored triangles has been characterized by Gallai back in the 1960s. More recently, Cǎda et al. and Fujita et al. independently determined the structure of edge-colored complete bipartite graphs containing no properly colored (Formula presented.). We characterize the structure of edge-colored complete graphs containing no properly colored even cycles, or equivalently, without a properly colored (Formula presented.) or (Formula presented.). In particular, we first deal with the simple case of 2-edge-colored complete graphs, using a result of Yeo. Next, for (Formula presented.), we define four classes of (Formula presented.) -edge-colored complete graphs without properly colored even cycles and prove that any (Formula presented.) -edge-colored complete graph without a properly colored even cycle belongs to one of these four classes.

AB - The structure of edge-colored complete graphs containing no properly colored triangles has been characterized by Gallai back in the 1960s. More recently, Cǎda et al. and Fujita et al. independently determined the structure of edge-colored complete bipartite graphs containing no properly colored (Formula presented.). We characterize the structure of edge-colored complete graphs containing no properly colored even cycles, or equivalently, without a properly colored (Formula presented.) or (Formula presented.). In particular, we first deal with the simple case of 2-edge-colored complete graphs, using a result of Yeo. Next, for (Formula presented.), we define four classes of (Formula presented.) -edge-colored complete graphs without properly colored even cycles and prove that any (Formula presented.) -edge-colored complete graph without a properly colored even cycle belongs to one of these four classes.

KW - complete graph

KW - edge-colored graph

KW - forbidden subgraph

KW - properly colored cycle

KW - UT-Hybrid-D

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

U2 - 10.1002/jgt.22684

DO - 10.1002/jgt.22684

M3 - Article

AN - SCOPUS:85105632340

SN - 0364-9024

VL - 98

SP - 110

EP - 124

JO - Journal of graph theory

JF - Journal of graph theory

IS - 1

ER -

Edge-colored complete graphs without properly colored even cycles: A full characterization

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this