Mathematics – Combinatorics
Scientific paper
2006-02-15
Mathematics
Combinatorics
23 pages, 0 figures
Scientific paper
In a graph whose edges are colored, a parity walk is a walk that uses each color an even number of times. The parity edge chromatic number p(G) of a graph G is the least k so that there is a coloring of E(G) using k colors that does not contain a parity path. The strong parity edge chromatic number p'(G) of G is the least k so that there is a coloring of E(G) using k colors with the property that every parity walk is closed. Our main result is to determine p'(K_n). Specifically, if m is the least power of two that is as large as n, then p'(K_n) has value m - 1. As a corollary, we strengthen a special case of an old result of Daykin and Lovasz. Other results include determining p(G) and p'(G) whenever G is a path, cycle, or of the form K_{2,n}, and an upper bound on p'(G) for the case that G is a complete bipartite graph. We conclude with a sample of open problems.
Bunde David P.
Milans Kevin
West Douglas B.
Wu Hehui
No associations
LandOfFree
Parity Edge-Coloring of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parity Edge-Coloring of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parity Edge-Coloring of Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-103350