Even edge colorings of a graph (Q5895486)
From MaRDI portal
scientific article; zbMATH DE number 3885933
Language | Label | Description | Also known as |
---|---|---|---|
English | Even edge colorings of a graph |
scientific article; zbMATH DE number 3885933 |
Statements
Even edge colorings of a graph (English)
0 references
1985
0 references
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)].
0 references
finite undirected simple graph
0 references
edge coloring
0 references
vertex chromatic number
0 references