Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420215 | Discrete Applied Mathematics | 2011 | 7 Pages |
Abstract
In an edge-colored graph, let dc(v)dc(v) be the number of colors on the edges incident to vv and let δc(G)δc(G) be the minimum dc(v)dc(v) over all vertices v∈Gv∈G. In this work, we consider sharp conditions on δc(G)δc(G) which imply the existence of properly edge-colored paths and cycles, meaning no two consecutive edges have the same color.
► We consider edge colorings of graphs with color degree conditions. ► Increasing color degree implies that properly colored cycles and paths exist. ► Large color degree implies that small properly colored cycles exist. ► Large color degree implies that vertices are connected by properly colored paths.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shinya Fujita, Colton Magnant,