Edge cover through edge coloring

Guantao Chen ; Songling Shan¹

¹Auburn University

The electronic journal of combinatorics, Tome 32 (2025) no. 2

Résumé

Let $G$ be a multigraph. A subset $F$ of $E(G)$ is an edge cover of $G$ if every vertex of $G$ is incident to an edge of $F$. The cover index, $\xi(G)$, is the largest number of edge covers into which the edges of $G$ can be partitioned. Clearly $\xi(G) \le \delta(G)$, the minimum degree of $G$. For $U\subseteq V(G)$, denote by $E^+(U)$ the set of edges incident to a vertex of $U$. When $|U|$ is odd, to cover all the vertices of $U$, any edge cover needs to contain at least $(|U|+1)/2$ edges from $E^+(U)$, indicating $ \xi(G) \le |E^+(U)|/ ((|U|+1)/2)$. Let $\rho_c(G)$, the co-density of $G$, be defined as the minimum of $|E^+(U)|/((|U|+1)/2)$ ranging over all $U\subseteq V(G)$, where $|U| \ge 3$ and $|U|$ is odd. Then $\rho_c(G)$ provides another upper bound on $\xi(G)$. Thus $\xi(G) \le \min\{\delta(G), \lfloor \rho_c(G) \rfloor \}$. For a lower bound on $\xi(G)$, in 1978, Gupta conjectured that $\xi(G) \ge \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \}$. Gupta himself verified the conjecture for simple graphs, and Cao et al. recently verified this conjecture when $\rho_c(G)$ is not an integer. In this paper, we confirm the conjecture when the maximum multiplicity of $G$ is at most two or $ \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \} \le 6$. The proof relies on a newly established result on edge colorings. The result holds independent interest and has the potential to significantly contribute towards resolving the conjecture entirely.

Détail

DOI : 10.37236/13163

Classification : 05C38
Mots-clés : edge cover, cover index, co-density, chromatic index