Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$

Kola, Srinivasa Rao ; Panigrahi, Pratima

Mathematica Bohemica, Tome 134 (2009) no. 1, pp. 77-86.

Résumé

Chartrand et al.\ (2004) have given an upper bound for the nearly antipodal chromatic number $ac'(P_n)$ as $\binom {n-2}2+2$ for $n \geq 9$ and have found the exact value of $ac'(P_n)$ for $n=5,6,7,8$. Here we determine the exact values of $ac'(P_n)$ for $n \geq 8$. They are $2p^2-6p+8$ for $n=2p$ and $2p^2-4p+6$ for $n=2p+1$. The exact value of the radio antipodal number $ac(P_n)$ for the path $P_n$ of order $n$ has been determined by Khennoufa and Togni in 2005 as $2p^2-2p+3$ for $n=2p+1$ and $2p^2-4p+5$ for $n=2p$. Although the value of $ac(P_n)$ determined there is correct, we found a mistake in the proof of the lower bound when $n=2p$ (Theorem $6$). However, we give an easy observation which proves this lower bound.

Détail

DOI : 10.21136/MB.2009.140642

Classification : 05C12, 05C15, 05C78
Keywords: radio $k$-coloring; span; radio $k$-chromatic number