The Neighbor-Locating-Chromatic Number of Pseudotrees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914787887153152 |
|---|---|
| author | Alcon, Liliana Gutierrez, Marisa Hernando, Carmen Mora, Mercè Pelayo, Ignacio M. |
| author_facet | Alcon, Liliana Gutierrez, Marisa Hernando, Carmen Mora, Mercè Pelayo, Ignacio M. |
| contents | A $k$-coloring of a graph $G$ is a partition of the set of vertices of $G$ into $k$ independent sets, which are called colors. A $k$-coloring is neighbor-locating if any two vertices belonging to the same color can be distinguished from each other by the colors of their respective neighbors. The neighbor-locating chromatic number $χ_{_{NL}}(G)$ is the minimum cardinality of a neighbor-locating coloring of $G$. In this paper, we determine the neighbor-locating chromatic number of paths, cycles, fans, and wheels. Moreover, a procedure to construct a neighbor-locating coloring of minimum cardinality for these families of graphs is given. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_11937 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | The Neighbor-Locating-Chromatic Number of Pseudotrees Alcon, Liliana Gutierrez, Marisa Hernando, Carmen Mora, Mercè Pelayo, Ignacio M. Combinatorics 05C15, 05C38, 05C69, 05C05 A $k$-coloring of a graph $G$ is a partition of the set of vertices of $G$ into $k$ independent sets, which are called colors. A $k$-coloring is neighbor-locating if any two vertices belonging to the same color can be distinguished from each other by the colors of their respective neighbors. The neighbor-locating chromatic number $χ_{_{NL}}(G)$ is the minimum cardinality of a neighbor-locating coloring of $G$. In this paper, we determine the neighbor-locating chromatic number of paths, cycles, fans, and wheels. Moreover, a procedure to construct a neighbor-locating coloring of minimum cardinality for these families of graphs is given. 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. |
| title | The Neighbor-Locating-Chromatic Number of Pseudotrees |
| topic | Combinatorics 05C15, 05C38, 05C69, 05C05 |
| url | https://arxiv.org/abs/1903.11937 |