Even edge colorings of a graph (Q5895486): Difference between revisions

It is shown that the minimum number of colors needed to paint the edges of a graph G so that in every cycle of G there is a nonzero even number of edges of at least one color is \(\lceil \log_ 2\chi (G)\rceil\), where \(\chi\) (G) denotes the vertex chromatic number of G, and \(\lceil \rceil\) denotes the least integer not less than the number inside. The restriction of this result to the case that G is a complete graph was conjectured by \textit{B. D. Acharya} [J. Comb. Theory, Ser. B 35, 78-79 (1983; Zbl 0505.05032)].