Even edge colorings of a graph

DOI10.1016/0095-8956(85)90094-2MaRDI QIDQ5895486zbMATH OpenOpenAlexFDO

Authors Noga Alon, Yoshimi Egawa

Publication date 1985

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(85)90094-2

zbMATH Keywords

edge coloringfinite undirected simple graphvertex chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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)].

Recommendations

• The chromatic index of graphs of even order with many edges
• Monochromatic even cycles
• scientific article; zbMATH DE number 4070929
• Parity and strong parity edge-colorings of graphs
• Cycle lengths and chromatic number of graphs

Cites work

• Even edge colorings of a graph

Cited in

(4)

• Local k-colorings of graphs and hypergraphs
• Decomposing hypergraphs into k-colorable hypergraphs
• scientific article; zbMATH DE number 2192169 (Why is no real title available?)
• Bounds for chromatic number in terms of even-girth and booksize

This page was built for publication: Even edge colorings of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895486)