Parity Edge-Coloring of Graphs
| dc.creator | Bunde, David P. | |
| dc.creator | Milans, Kevin | |
| dc.creator | West, Douglas B. | |
| dc.creator | Wu, Hehui | |
| dc.date | 2006-02-15 | |
| dc.date.accessioned | 2026-07-07T07:03:28Z | |
| dc.date.available | 2026-07-07T07:03:28Z | |
| dc.description | 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. | |
| dc.description | 23 pages, 0 figures | |
| dc.identifier | https://arxiv.org/abs/math/0602341 | |
| dc.identifier | http://arxiv.org/abs/math/0602341 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/108986 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 | |
| dc.title | Parity Edge-Coloring of Graphs | |
| dc.type | text |