×

Irregular edge-colorings of sums of cycles of even lengths. (English) Zbl 1143.05024

Authors’ abstract: P. Wittmann showed that for the irregular coloring number \(c(G)\) of a simple 2-regular graph of order \(n\) the inequality \(c(G)\leq\sqrt{2n}+ O(1)\) holds. We determine the exact value of this number in the case when the 2-regular graph consists of cycles of even lengths. For this purpose we consider decompositions of several classes of graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite