zbMATH — the first resource for mathematics

Infinitely many trees with maximum number of holes zero, one, and two. (English) Zbl 1437.05075
Summary: An \(L(2,1)\)-coloring of a simple connected graph \(G\) is an assignment \(f\) of nonnegative integers to the vertices of \(G\) such that \(|f(u)-f(v)| \geqslant 2\) if \(d(u,v)=1\) and \(|f(u)-f(v)|\geqslant 1\) if \(d(u,v)=2\) for all \(u,v\in V(G)\), where \(d(u,v)\) denotes the distance between \(u\) and \(v\) in \(G\). The span of \(f\) is the maximum color assigned by \(f\). The span of a graph \(G\), denoted by \(\lambda (G)\), is the minimum of span over all \(L(2,1)\)-colorings on \(G\). An \(L(2,1)\)-coloring of \(G\) with span \(\lambda(G)\) is called a span coloring of \(G\). An \(L(2,1)\)-coloring \(f\) is said to be irreducible if there exists no \(L(2,1)\)-coloring g such that \(g(u) \leqslant f(u)\) for all \(u \in V(G)\) and \(g(v) < f(v)\) for some \(v \in V(G)\). If \(f\) is an \(L(2,1)\)-coloring with span \(k\), then \(h \in\{0,1, 2, \dots, k\}\) is a hole if there is no \(v \in V(G)\) such that \(f(v)=h\). The maximum number of holes over all irreducible span colorings of \(G\) is denoted by \(H_\lambda (G)\). A tree \(T\) with maximum degree \(\Delta\) having span \(\Delta +1\) is referred to as Type-I tree; otherwise it is Type-II. In this paper, we give a method to construct infinitely many trees with at least one hole from a one-hole tree and infinitely many two-hole trees from a two-hole tree. Also, using the method, we construct infinitely many Type-II trees with maximum number of holes one and two. Further, we give a sufficient condition for a Type-II tree with maximum number of holes zero.
05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C05 Trees
Full Text: DOI
[1] Griggs, J. R.; Yeh, R. K., Labeling graphs with a condition at distance 2, SIAM Journal on Discrete Mathematics, 5, 4, 586-595, (1992) · Zbl 0767.05080
[2] Wang, W.-F., The L(2,1)-labelling of trees, Discrete Applied Mathematics, 154, 3, 598-603, (2006) · Zbl 1088.05066
[3] Zhai, M.-q.; Lu, C.-h.; Shu, J.-l., A note on L(2,1)-labelling of trees, Acta Mathematicae Applicatae Sinica, 28, 2, 395-400, (2012) · Zbl 1355.05219
[4] Mandal, N.; Panigrahi, P., Solutions of some L(2,1)-coloring related open problems, Discussiones Mathematicae Graph Theory, 36, 2, 279-297, (2016) · Zbl 1338.05089
[5] Wood, C. A.; Jacob, J., A complete L(2,1)-span characterization for small trees, AKCE International Journal of Graphs and Combinatorics, 12, 1, 26-31, (2015) · Zbl 1332.05125
[6] Fishburn, P. C.; Roberts, F. S., No-hole L(2,1)-colorings, Discrete Applied Mathematics, 130, 3, 513-519, (2003) · Zbl 1032.05046
[7] Fishburn, P. C.; Laskar, R. C.; Roberts, F. S.; Villalpando, J., Parameters of L(2,1)-coloring
[8] Laskar, R. C.; Matthews, G. L.; Novick, B.; Villalpando, J., On irreducible no-hole L(2,1)-coloring of trees, Networks. An International Journal, 53, 2, 206-211, (2009) · Zbl 1167.05026
[9] Laskar, R.; Eyabi, G., Holes in L(2,1)-coloring on certain classes of graphs, AKCE International Journal of Graphs and Combinatorics, 6, 2, 329-339, (2009) · Zbl 1210.05033
[10] Kola, S. R.; Gudla, B.; P. K., N., Some classes of trees with maximum number of holes two, AKCE International Journal of Graphs and Combinatorics, (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.