IJPAM: Volume 76, No. 1 (2012)

INCIDENCE COLORINGS OF THE POWERS OF CYCLES

Keaitsuda Nakprasit$^1$, Kittikorn Nakprasit$^2$
$^{1,2}$Department of Mathematics
Faculty of Science
Khon Kaen University
40002, THAILAND


Abstract. The incidence chromatic number of a graph $G,$ denoted by $\chi_i(G),$ is the smallest positive integer of colors such that $G$ has an incidence coloring. We determine for all $n$ except $2k^2-3k+1$ cases for each $k\geq 3$ that if $n$ is divisible by $2k+1$, then $\chi_i(C^k_n)=2k+1$, otherwise $\chi_i(C^k_n)=2k+2.$ Moreover, we show that if $n$ is divisible by 5, then $\chi_i(C^2_n)= 5.$ Otherwise $\chi_i(C^2_n)= 6.$

Received: February 27, 2012

AMS Subject Classification: 05C15, 05C35

Key Words and Phrases: incidence coloring, powers of cycles

Download paper from here.



Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2012
Volume: 76
Issue: 1