Edge cover through edge coloring

DOI10.37236/13163MaRDI QIDQ6977164zbMATH OpenFDO

Authors Guantao Chen, Songling Shan

Publication date 30 May 2025

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.37236/13163

zbMATH Keywords

chromatic indexco-densitycover indexedge cover

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

This paper makes progress on \textit{R. P. Gupta}'s 1978 conjecture [Lect. Notes Math. 642, 204--215 (1978; Zbl 0369.05033)] that \(\xi(G) \geq \min\{\delta(G)-1, \lfloor p_c(G) \rfloor\}\) for any multigraph \(G\), where \(\xi(G)\) is the cover index and \(p_c(G)\) the co-density. The authors confirm the conjecture when the maximum multiplicity of \(G\) is at most two or \(\min\{\delta(G) - 1, \lfloor p_c(G) \rfloor\} \leq 6\), assuming the Goldberg-Seymour conjecture. The proof introduces a new edge-coloring technique that may be of independent interest. These results significantly advance our understanding of edge cover partitions in multigraphs, though the full conjecture remains open.

Cites work

• On decompositions of a multi-graph into spanning subgraphs
• On Gupta’s Codensity Conjecture
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On the chromatic index and the cover index of a multigraph

This page was built for publication: Edge cover through edge coloring

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