The f-Chromatic Index of Claw-free Graphs Whose f-Core is 2-regular

Abstract

Let $G$ be a graph and $f:V(G)\to \mathbb{N}$ be a function. An $f$-coloring of a graph $G$ is an edge coloring such that each color appears at each vertex $v\in V(G)$ at most $f(v)$ times. The minimum number of colors needed to $f$-color $G$ is called the $f$-chromatic index of $G$ and is denoted by ${\chi }_f^{\prime }(G)$. It was shown that for every graph $G$, ${\Delta }_f(G)\le {\chi }_f^{\prime }(G)\le {\Delta }_f(G)+1$, where ${\Delta }_f(G)={\max }_{v\in V(G)}\lceil \frac{d_G(v)}{f(v)}\rceil$. A graph $G$ is said to be $f$-Class $1$ if ${\chi }_f^{\prime }(G)={\Delta }_f(G)$, and $f$-Class $2$, otherwise. Also, $G_{{\Delta }_f}$ is the induced subgraph of $G$ on $\{v\in V(G):\frac{d_G(v)}{f(v)}={\Delta }_f(G)\}$. In this paper, we show that if $G$ is a connected graph with $\Delta (G_{{\Delta }_f})\le 2$ and $G$ has an edge cut of size at most ${\Delta }_f(G)-2$ which is a matching or a star, then $G$ is $f$-Class $1$. Also, we prove that if $G$ is a connected graph and every connected component of $G_{{\Delta }_f}$ is a unicyclic graph or a tree and $G_{{\Delta }_f}$ is not $2$-regular, then $G$ is $f$-Class $1$. Moreover, we show that except one graph, every connected claw-free graph $G$ whose $f$-core is $2$-regular with a vertex $v$ such that $f(v)\ne 1$ is $f$-Class $1$.

17 pages, 8 figures