MATHEMATICA BOHEMICA, Vol. 127, No. 1, pp. 57-69 (2002)

Radio antipodal colorings of graphs

Gary Chartrand, David Erwin, Ping Zhang

Gary Chartrand, David Erwin, Ping Zhang, Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008 USA, e-mail:

Abstract: A radio antipodal coloring of a connected graph $G$ with diameter $d$ is an assignment of positive integers to the vertices of $G$, with $x \in V(G)$ assigned $c(x)$, such that $$ d(u, v) + |c(u) -c(v)| \geq d $$ for every two distinct vertices $u$, $v$ of $G$, where $d(u, v)$ is the distance between $u$ and $v$ in $G$. The radio antipodal coloring number $\ac (c)$ of a radio antipodal coloring $c$ of $G$ is the maximum color assigned to a vertex of $G$. The radio antipodal chromatic number $\ac (G)$ of $G$ is $\min \{\ac (c)\}$ over all radio antipodal colorings $c$ of $G$. Radio antipodal chromatic numbers of paths are discussed and upper and lower bounds are presented. Furthermore, upper and lower bounds for radio antipodal chromatic numbers of graphs are given in terms of their diameter and other invariants.

Keywords: radio antipodal coloring, radio antipodal chromatic number, distance

Classification (MSC2000): 05C78, 05C12, 05C15

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number]
© 2005 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition