IJPAM: Volume 102, No. 2 (2015)

SOME GRAPHS IN $C_f2$ BASED ON $f$-COLORING

Adiwijaya$^1$, A.N.M. Salman$^2$, O. Serra$^3$, D. Suprijanto$^4$, E.T. Baskoro$^5$
$^1$Telkom University
Jl. Telekomunikasi 1, Bandung 40257, INDONESIA
$^{2,4,5}$Bandung Institute of Technology
Jl. Ganesa 10, Bandung 40132, INDONESIA
$^3$Universitat Politècnica de Catalunya (UPC)
C/Jordi Girona 1-3, E-08034 Barcelona, SPAIN


Abstract. Let $G=(V,E)$ be a graph and $f:V\to Z^{+}$a positive integer be a function. An f-coloring of $G$ is a coloring of the edges such that every vertex $v \in V$ is incident to at most $f(v)$ edges of the same color. The minimum number of colors of an $f$-coloring of $G$ is the f-chromatic index $\chi_f'(G)$ of $G$. Based on the $f$-chromatic index, a graph $G$ can be either in class $C_f1$, if $\chi_f'(G)= \Delta_f(G)$, or in class $C_f2$, if $\chi_f'(G)= \Delta_f(G)+1$, where $\Delta_f(G)=\max_{x\in V} \lceil d(v)/f(v)\rceil$. In this paper, we give some sufficient conditions for a graph to be in $C_f2$. One of the results is a generalization of a theorem by Zhang et al. (2008). Moreover, we show that, when $f$ is constant and a divisor of $(n-1)$, a maximal subgraph of the complete graph $K_n$ which is in class $C_f1$ has precisely ${n\choose 2}-\Delta_f(K_n)/2$ edges.

Received: January 20, 2015

AMS Subject Classification: 05C15

Key Words and Phrases: edge coloring, $f$-coloring, $f$-chromatic index

Download paper from here.



DOI: 10.12732/ijpam.v102i2.3 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2015
Volume: 102
Issue: 2
Pages: 201 - 207


$C_f2$ BASED ON $f$-COLORING%22&as_occt=any&as_epq=&as_oq=&as_eq=&as_publication=&as_ylo=&as_yhi=&as_sdtAAP=1&as_sdtp=1" title="Click to search Google Scholar for this entry" rel="nofollow">Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).