Premium
A complete bipartite graph without properly colored cycles of length four
Author(s) -
Čada Roman,
Ozeki Kenta,
Yoshimoto Kiyoshi
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22480
Subject(s) - combinatorics , mathematics , bipartite graph , corollary , complete bipartite graph , robertson–seymour theorem , monochromatic color , complete graph , discrete mathematics , graph factorization , colored , edge coloring , graph , 1 planar graph , chordal graph , graph power , line graph , materials science , composite material , botany , biology
A subgraph of an edge‐colored graph is said to be properly colored, or shortly PC, if any two adjacent edges have different colors. Fujita, Li, and Zhang gave a decomposition theorem for edge‐colorings of complete bipartite graphs without PC C 4 . However, their decomposition just focuses on a local structure. In this paper, we give a new and global decomposition theorem for edge‐colorings of complete bipartite graphs without PC C 4 . Our decomposition gives a corollary on the existence of a monochromatic star with almost sharp bound.