A Note on Edge Coloring of Graphs

Abstract

Let $G$ be a graph with minimum degree $\delta (G)$. R.P. Gupta proved two interesting results: 1) A bipartite graph $G$ has a 5-edge-coloring in which all 6 colors appear at each vertex. 2) If $G$ is a simple graph with $\delta (G)>1$, then $G$ has a $(\delta –1)$-edge-coloring in which all $(\delta –1)$ colors appear at each vertex. Let $t$ be a positive integer. In this paper, we extend the first result by showing that for every bipartite graph, there exists a $t$-edge coloring such that at each vertex $v$, $min\{t,d(v)\}$ colors appear. Additionally, we demonstrate that if $G$ is a graph, then the edges of $G$ can be colored using $t$ colors, where for each vertex $v$, the number of colors appearing at $v$ is at least $min\{t,d(v)–1\}$, generalizing the second result.