A complete bipartite graph without properly colored cycles of length four
A complete bipartite graph without properly colored cycles of length four
复制标题
DOI：
10.1002/jgt.22480
复制
发表时间：
2019-07
影响因子：
0.9
通讯作者：
Roman Cada;K. Ozeki;Kiyoshi Yoshimoto
中科院分区：
文献类型：
--
作者：
Roman Cada;K. Ozeki;Kiyoshi Yoshimoto
如果任意两个相邻的边具有不同的颜色，则称一个带色边图的子图是带色的，或者简称PC。Fujita, Li， Zhang给出了不含pcc4的完全二部图边着色的分解定理。然而，它们的分解只关注于局部结构。本文给出了不含pcc4的完全二部图边着色的一个新的全局分解定理。我们的分解给出了单色星存在近似锐界的推论。
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 C4 . 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 C4 . Our decomposition gives a corollary on the existence of a monochromatic star with almost sharp bound.