Decomposing edge-colored graphs under color degree constraints

Abstract

For an edge-colored graph $G$, the minimum color degree of $G$ means the minimum number of colors on edges which are adjacent to each vertex of $G$. We prove that if $G$ is an edge-colored graph with minimum color degree at least $5$ then $V(G)$ can be partitioned into two parts such that each part induces a subgraph with minimum color degree at least $2$. We show this theorem by proving a much stronger form. Moreover, we point out an important relationship between our theorem and Bermond-Thomassen's conjecture in digraphs.

11 pages, 4 figures

References in corpus (1)

• Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs

Cited by in corpus (1)

• Decomposing $C_4$-free graphs under degree constraints