Get all the updates for this publication

Journal

On relationship between Hamiltonian path and holes in L(3,2,1)-coloring of minimum spanPublished in Elsevier B.V.

2017

Volume: 222

Pages: 227 - 234

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.

Postprint Version

Content may be subject to copyright,Check License© This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc... ...© This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/

About the journal

Journal | Data powered by TypesetDiscrete Applied Mathematics |
---|---|

Publisher | Data powered by TypesetElsevier B.V. |

ISSN | 0166-218X |