Article in volume
Authors:
Liliana Alcón
CMaLP, Universidad Nacional de La Plata
La Plata, Argentina
and CONICET, Argentina
email: liliana@mate.unlp.edu.ar
Title:
The neighbor-locating-chromatic number of trees and unicyclic graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 659-675
Received: 2020-05-24 , Revised: 2021-01-09 , Accepted: 2021-01-09 , Available online: 2021-02-06 , https://doi.org/10.7151/dmgt.2392
Abstract:
A $k$-coloring of a graph is neighbor-locating if any two vertices with
the same color can be distinguished by the colors of their respective neighbors,
that is, the sets of colors of their neighborhoods are different. The
neighbor-locating chromatic number $\chi_{_{NL}}(G)$ is the minimum
$k$ such that a neighbor-locating $k$-coloring of $G$ exists. In this paper,
we give upper and lower bounds on the neighbor-locating chromatic number in
terms of the order and the degree of the vertices for unicyclic graphs and trees.
We also obtain tight upper bounds on the order of trees and unicyclic graphs in
terms of the neighbor-locating chromatic number. Further partial results for
trees are also established.
Keywords:
coloring, location, neighbor-locating coloring, unicyclic graph, tree
References:
- L. Alcon, M. Gutierrez, C. Hernando, M. Mora and I.M. Pelayo, Neighbor-locating colorings in graphs, Theoret. Comput. Sci. 806 (2020) 144–155.
https://doi.org/10.1016/j.tcs.2019.01.039 - L. Alcon, M. Gutierrez, C. Hernando, M. Mora and I.M. Pelayo, The neighbor-locating-chromatic number of pseudotrees (2019).
arXiv: 1903.11937v2 - E.T. Baskoro and A. Asmiati, Characterizing all trees with locating-chromatic number $ 3$, Electron. J. Graph Theory Appl. 1 (2013) 109–117.
https://doi.org/10.5614/ejgta.2013.1.2.4 - A. Behtoei and M. Anbarloei, The locating chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40 (2014) 1491–1504.
- A. Behtoei and M. Anbarloei, A bound for the locating chromatic numbers of trees, Trans. Comb. 4 (2015) 31–41.
- A. Behtoei and B. Omoomi, On the locating chromatic number of Kneser graphs, Discrete Appl. Math. 159 (2011) 2214–2221.
https://doi.org/10.1016/j.dam.2011.07.015 - G.G. Chappell, J. Gimbel and C. Hartman, Bounds on the metric and partition dimensions of a graph, Ars Combin. 88 (2008) 349–366.
- G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater and P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002) 89–101.
- G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater and P. Zhang, Graphs of order $n$ with locating-chromatic number $n-1$, Discrete Math. 269 (2003) 65–79.
https://doi.org/10.1016/S0012-365X(02)00829-4 - G. Chartrand, L. Lesniak and P. Zhang, Graphs and digraphs, Fifth Edition (Chapman and Hall/CRC Press, Taylor and Francis Group, 2011).
- G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math. 59 (2000) 45–54.
https://doi.org/10.1007/PL00000127 - M. Fehr, S. Gosselin and O.R. Oellermann, The partition dimension of Cayley digraphs, Aequationes Math. 71 (2006) 1–18.
https://doi.org/10.1007/s00010-005-2800-z - H. Fernau, J.A. Rodríguez-Velázquez and I. González-Yero, On the partition dimension of unicyclic graphs, Bull. Math. Soc. Sci. Math. Roumanie 57(105) (2014) 381–391.
- C. Grigorious, S. Stephen, R. Rajan and M. Miller, On the partition dimension of circulant graphs, Comput. J. 60 (2017) 180–184.
https://doi.org/10.1093/comjnl/bxw079 - F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
- C. Hernando, M. Mora and I.M. Pelayo, Resolving dominating partitions in graphs, Discrete Appl. Math. 266 (2019) 237–251.
https://doi.org/10.1016/j.dam.2018.12.001 - J.A. Rodríguez-Velázquez, I. González Yero and M. Lemańska, On the partition dimension of trees, Discrete Appl. Math. 166 (2014) 204–209.
https://doi.org/10.1016/j.dam.2013.09.026 - P.J. Slater, Leaves of trees, in: Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer. 14 (1975) 549–559.
- P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988) 445–455.
- D. Welyyanti, E.T. Baskoro, Darmaji, R. Simanjuntak and S. Uttunggadewa, On locating-chromatic number of complete n-ary tree, AKCE Int. J. Graphs Comb. 10 (2013) 309–315.
Close