The f-Chromatic Index of a Graph Whose f-Core Has Maximum Degree 2

Akbari, S. ; Chavooshi, M. ; Ghanbari, M. ; Zare, S.

Canadian mathematical bulletin, Tome 56 (2013) no. 3, pp. 449-458

Résumé

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 $X'\left( G \right)$ . It is well known that $\Delta \left( G \right)\,\le \,\mathcal{X}'\left( G \right)\,\le \Delta \left( G \right)\,+\,1$ , for any graph $G$ , where $\Delta \left( G \right)$ denotes the maximum degree of $G$ . A graph $G$ is said to be class 1 if ${\mathcal{X}}'\left( G \right)\,=\,\Delta \left( G \right)$ and class 2 if ${\mathcal{X}}'\left( G \right)\,=\,\Delta \left( G \right)\,+\,1$ . Also, ${{G}_{\Delta }}$ is the induced subgraph on all vertices of degree $\Delta \left( G \right)$ . Let $f:\,V\left( G \right)\,\to \mathbb{N}$ be a function. An $f$ -coloring of a graph $G$ is a coloring of the edges of $E\left( G \right)$ such that each color appears at each vertex $v\,\in \,V\left( G \right)$ at most $f\left( v \right)$ times. The minimum number of colors needed to $f$ -color $G$ is called the $f$ -chromatic index of $G$ and is denoted by ${{{\mathcal{X}}'}_{f}}\left( G \right)$ . It was shown that for every graph $G,\,{{\Delta }_{f}}\,\left( G \right)\,\le \,{{\mathcal{X}}^{\prime }}_{f}\left( G \right)\,\le \,{{\Delta }_{f}}\,\left( G \right)\,+\,1$ , where ${{\Delta }_{f}}\left( G \right)\,=\,{{\max }_{v\in \left( G \right)}}\,\left\lceil {{{d}_{G}}\left( v \right)}/{f\left( v \right)}\; \right\rceil $ . A graph $G$ is said to be $f$ -class 1 if ${{\mathcal{X}}^{\prime }}_{f}\left( G \right)\,=\,{{\Delta }_{f}}\left( G \right)$ , and $f$ -class 2, otherwise. Also, ${{G}_{{{\Delta }_{f}}}}$ is the induced subgraph of $G$ on $\left\{ v\,\in \,V\left( G \right)\,:\,{{{d}_{G}}\left( V \right)}/{f\left( v \right)}\;\,=\,{{\Delta }_{f}}\left( G \right) \right\}$ . 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 \left( G \right)\,=\,\Delta \left( G \right)-1$ , where $\delta \left( G \right)$ 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 $\left| {{G}_{{{\Delta }_{f}}}} \right|\,\le \,4$ .

Détail

DOI : 10.4153/CMB-2012-046-3

Mots-clés : 05C15, 05C38, ƒ-coloring, ƒ-core, ƒ-class 1

Bibliographie

[1] [1] Akbari, S., Cariolaro, D., Chavooshi, M., Ghanbari, M., and Zare, S., Some criteria for a graph to be class 1. Discrete Math. 312 (2012), 2593–2598. Google Scholar | DOI

[2] [2] Chetwynd, A. G. and Hilton, A.J.W., Regular graphs of high degree are 1-factorizable. Proc. London Math. Soc. 50 (1985), 193–196. Google Scholar | DOI

[3] [3] Chetwynd, A. G. and Hilton, A.J.W., The chromatic index of graphs with at most four vertices of maximum degree. Congr. Numer. 43 (1984), 221–248. Google Scholar

[4] [4] Coffman, E. G., Garey, M. R., Johnson, D. S., and LaPaugh, A. S., Scheduling file transfers. SIAM J. Comput. 14 (1985), 744–780. Google Scholar | DOI

[5] [5] Hakimi, S. L. and Kariv, O., A generalization of edge-coloring in graphs. J. Graph Theory 10 (1986), 139–154. Google Scholar | DOI

[6] [6] Hilton, A. J.W. and Zhao, C., The chromatic index of a graph whose core has maximum degree two. Discrete Math. 101 (1992), 135–147. Google Scholar | DOI

[7] [7] Krawczyk, H. and Kubale, M., An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans. Comput. 34 (1985), 869–872. Google Scholar

[8] [8] Liu, G., Hou, J., and Cai, J., Some results about f -critical graphs. Published online inWiley InterScience, 2007). Google Scholar | DOI

[9] [9] Nakano, S., Nishizeki, T., and Saito, N., On the f -coloring of multigraphs. IEEE Trans Circuits Systems 35 (1988), 345–353. Google Scholar | DOI

[10] [10] Vizing, V. G., The chromatic class of a multigraph. Kibernetika 3 (1965), 29–39. Google Scholar

[11] [11] Zhang, X. and Liu, G., A class of graphs of f -class 1. In: International Conference on Computational Science (ICCS 2007, Beijing, China), LNCS 4489 (2007), 362–369. Google Scholar

[12] [12] Zhang, X. and Liu, G., Some graphs of class 1 for f -colorings. Appl. Math. Letters 21 (2008), 23–39. Google Scholar | DOI

[13] [13] Zhang, X., Wang, J., and Liu, G., The classification of regular graphs on f -colorings. Ars. Combin. 86 (2008), 273–280. Google Scholar