Abstract view
The $f$Chromatic Index of a Graph Whose $f$Core has Maximum Degree $2$


Published:20130320
Printed: Sep 2013
S. Akbari,
Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran
M. Chavooshi,
Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran
M. Ghanbari,
School of Mathematics, Institute for Studies in Theoretical Physics and Mathematics, P.O. Box 193955746, Tehran, Iran
S. Zare,
Department of Mathematical Sciences, Amirkabir University of Technology, Tehran, Iran
Abstract
Let $G$ be a graph. The minimum number of colors needed to color the edges of
$G$ is called the chromatic index of $G$ and is denoted by $\chi'(G)$.
It is wellknown that $\Delta(G) \leq \chi'(G) \leq \Delta(G)+1$, for any
graph $G$, where $\Delta(G)$ denotes the maximum degree of $G$. A graph $G$ is said to be
Class $1$ if $\chi'(G) = \Delta(G)$ and Class $2$ if
$\chi'(G) = \Delta(G) + 1$. Also, $G_\Delta$ is the induced subgraph on all vertices of degree $\Delta(G)$.
Let $f:V(G)\rightarrow \mathbb{N}$ be a function.
An $f$coloring of a graph $G$ is a coloring of the edges
of $E(G)$ 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}(G)$. It was shown that for every graph $G$, $\Delta_{f}(G)\le \chi'_{f}(G)\le \Delta_{f}(G)+1$, where $\Delta_{f}(G)=\max_{v\in V(G)} \big\lceil \frac{d_G(v)}{f(v)}\big\rceil$. A graph $G$ is said to be $f$Class $1$ if $\chi'_{f}(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)\}$.
Hilton and Zhao showed that if $G_{\Delta}$ has maximum degree two and $G$ is Class $2$, then $G$ is critical, $G_{\Delta}$ is a disjoint union of cycles and $\delta(G)=\Delta(G)1$, where $\delta(G)$ denotes the minimum degree of $G$, respectively. In this paper, we generalize this theorem to $f$coloring of graphs. Also, we determine the $f$chromatic index of a connected graph $G$ with $G_{\Delta_f}\le 4$.