Sequential edge-coloring on the subset of vertices of almost regular graphs

Abstract

Let $G$ be a graph and $R\subseteq V(G)$. A proper edge-coloring of a graph $G$ with colors $1,\dots ,t$ is called an $R$-sequential $t$-coloring if the edges incident to each vertex $v\in R$ are colored by the colors $1,\dots ,d_G(v)$, where $d_G(v)$ is the degree of the vertex $v$ in $G$. In this note, we show that if $G$ is a graph with $\Delta (G)-\delta (G)\le 1$ and ${\chi }^{\prime }(G)=\Delta (G)=r$ ($r\ge 3$), then $G$ has an $R$-sequential $r$-coloring with $|R|\ge \lceil \frac{(r-1)n_r+n}{r}\rceil$, where $n=|V(G)|$ and $n_r=|\{v\in V(G):d_G(v)=r\}|$. As a corollary, we obtain the following result: if $G$ is a graph with $\Delta (G)-\delta (G)\le 1$ and ${\chi }^{\prime }(G)=\Delta (G)=r$ ($r\ge 3$), then ${\Sigma }^{\prime }(G)\le \lfloor \frac{2n_r(2r-1)+n(r-1)(r^2+2r-2)}{4r}\rfloor$, where ${\Sigma }^{\prime }(G)$ is the edge-chromatic sum of $G$.

4 pages

References in corpus (1)

• Interval colorings of edges of a multigraph