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 journalArticleAcademicpeer-review

1 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 languageEnglish
Pages (from-to)110-124
Number of pages15
JournalJournal of graph theory
Volume98
Issue number1
DOIs
Publication statusPublished - Sep 2021

Keywords

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

Fingerprint

Dive into the research topics of 'Edge-colored complete graphs without properly colored even cycles: A full characterization'. Together they form a unique fingerprint.

Cite this