Geodesic
The neighbor-locating-chromatic number of trees and unicyclic graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 659-675 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 χ_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 
@article{DMGT_2023_43_3_a4,
     author = {Alcon, Liliana and Gutierrez, Marisa and Hernando, Carmen and Mora, Merc\'e and Pelayo, Ignacio},
     title = {The neighbor-locating-chromatic number of trees and unicyclic graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {659--675},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a4/}
}
TY  - JOUR
AU  - Alcon, Liliana
AU  - Gutierrez, Marisa
AU  - Hernando, Carmen
AU  - Mora, Mercé
AU  - Pelayo, Ignacio
TI  - The neighbor-locating-chromatic number of trees and unicyclic graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 659
EP  - 675
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a4/
LA  - en
ID  - DMGT_2023_43_3_a4
ER  - 
%0 Journal Article
%A Alcon, Liliana
%A Gutierrez, Marisa
%A Hernando, Carmen
%A Mora, Mercé
%A Pelayo, Ignacio
%T The neighbor-locating-chromatic number of trees and unicyclic graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 659-675
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a4/
%G en
%F DMGT_2023_43_3_a4
Alcon, Liliana; Gutierrez, Marisa; Hernando, Carmen; Mora, Mercé; Pelayo, Ignacio. The neighbor-locating-chromatic number of trees and unicyclic graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 659-675. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a4/

[1] 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

[2] L. Alcon, M. Gutierrez, C. Hernando, M. Mora and I.M. Pelayo, The neighbor-locating-chromatic number of pseudotrees (2019). arXiv: 1903.11937v2

[3] 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

[4] A. Behtoei and M. Anbarloei, The locating chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40 (2014) 1491–1504.

[5] A. Behtoei and M. Anbarloei, A bound for the locating chromatic numbers of trees, Trans. Comb. 4 (2015) 31–41.

[6] 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

[7] G.G. Chappell, J. Gimbel and C. Hartman, Bounds on the metric and partition dimensions of a graph, Ars Combin. 88 (2008) 349–366.

[8] 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.

[9] 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

[10] G. Chartrand, L. Lesniak and P. Zhang, Graphs and digraphs, Fifth Edition (Chapman and Hall/CRC Press, Taylor and Francis Group, 2011).

[11] 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

[12] 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

[13] 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.

[14] 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

[15] F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.

[16] 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

[17] 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

[18] P.J. Slater, Leaves of trees, in: Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer. 14 (1975) 549–559.

[19] P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988) 445–455.

[20] 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.