A classification of edge-colored graphs based on properly colored walks

Abstract A properly colored walk in an edge-colored graph is a walk such that consecutive edges are of distinct colors. In this paper, based on a transformation from directed graphs to edge-colored graphs, we classified edge-colored graphs into three families: degenerate edge-colored graphs, semi-degenerate edge-colored graphs and non-degenerate graphs. By a polynomial-time computable parameter related to properly colored walks, we gave a characterization of these three families. Applying this characterization, we slightly strengthened Yeo’s Theorem (Every edge-colored graph G containing no PC cycle contains a vertex z ∈ V ( G ) such that each component of G − z is joint to z with at most one color, Yeo, 1997).