X
On relationship between Hamiltonian path and holes in L(3,2,1)-coloring of minimum span
Published in Elsevier B.V.
2017
Volume: 222

Pages: 227 - 234
Abstract
The L(2,1)-coloring and L(3,2,1)-coloring on a finite simple connected graph G originate from frequency assignment problem. Any L(2,1)-coloring on G of minimum possible span is a λ2,1-coloring of G and its span is the λ2,1-number of G, denoted by λ2,1(G). Any integer i, 0<i<λ2,1(G), which is left unused as a color in a λ2,1-coloring L, is a hole in L. The λ3,2,1-number of G, λ3,2,1-coloring of G and holes in a λ3,2,1-coloring are defined in a similar manner. In their paper Georges et al. (1994) referred a hole i as a gap if |Li−1|=1=|Li+1|, Lj being the set of vertices colored j by L, and the vertices in Li−1∪Li+1 are adjacent. They showed if G admits a λ2,1-coloring without any gap, then the complement Gc has a Hamiltonian path. We first explore similar phenomenon in the perspective of L(3,2,1)-coloring, a natural generalization of L(2,1)-coloring problem. Towards this, we coin a term 2-gap. Formally, a λ3,2,1-coloring Lˆ on G is said to have a 2-gap {i+1,i+2} if Lˆ has two consecutive holes i+1, i+2 and |Lˆi|=1=|Lˆi+3|, where Lˆj is the set of vertices colored j by Lˆ. We prove if G admits a λ3,2,1-coloring without any 2-gap, then Gc has a Hamiltonian path. But investigating the converse of this result poses an intriguing combinatorial problem. However, after exploring various interesting features of a 2-gap, we give a class of finite simple connected graphs for which the converse is true. For the same class of graphs, a characterization of the L(3,2,1)-coloring problem is given as an application. © 2017 Elsevier B.V.