New bounds and constructions for neighbor-locating colorings of graphs

DOI10.1007/978-3-031-25211-2_9MaRDI QIDQ6132528zbMATH OpenOpenAlexFDO

Authors Dipayan Chakraborty, Florent Foucaud, Soumen Nandi, Sagnik Sen, D. K. Supraja

Publication date 17 August 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.13557

zbMATH Keywords

coloringlocation problemidentification problemneighbor-locating coloringneighbor-locating chromatic number

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: A proper $k$-coloring of a graph $G$ is a emph{neighbor-locating $k$-coloring} if for each pair of vertices in the same color class, the sets of colors found in their neighborhoods are different. The neighbor-locating chromatic number $ch{i}_{NL}(G)$ is the minimum $k$ for which $G$ admits a neighbor-locating $k$-coloring. A proper $k$-coloring of a graph $G$ is a emph{locating $k$-coloring} if for each pair of vertices $x$ and $y$ in the same color-class, there exists a color class $S_i$ such that $d(x,S_i)eqd(y,S_i)$. The locating chromatic number $ch{i}_L(G)$ is the minimum $k$ for which $G$ admits a locating $k$-coloring. It follows that $chi(G)leqch{i}_L(G)leqch{i}_{NL}(G)$ for any graph $G$, where $chi(G)$ is the usual chromatic number of $G$. We show that for any three integers $p,q,r$ with $2leqpleqqleqr$ (except when $2=p=q<r$), there exists a connected graph $G_{p,q,r}$ with $chi(G_{p,q,r})=p$, $ch{i}_L(G_{p,q,r})=q$ and $ch{i}_{NL}(G_{p,q,r})=r$. We also show that the locating chromatic number (resp., neighbor-locating chromatic number) of an induced subgraph of a graph $G$ can be arbitrarily larger than that of $G$. Alcon extit{et al.} showed that the number $n$ of vertices of $G$ is bounded above by $k(2^{k-1}-1)$, where $ch{i}_{NL}(G)=k$ and $G$ is connected (this bound is tight). When $G$ has maximum degree $Delta$, they also showed that a smaller upper-bound on $n$ of order $k^{Delta+1}$ holds. We generalize the latter by proving that if $G$ has order $n$ and at most $an+b$ edges, then $n$ is upper-bounded by a bound of the order of $k^{2a+1}+2b$. Moreover, we describe constructions of such graphs which are close to reaching the bound.

Cites work

• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 1869706 (Why is no real title available?)
• A bound for the locating chromatic number of trees
• Graphs of order \(n\) with locating-chromatic number \(n-1\)
• How complex are random graphs in first order logic?
• Locally identifying coloring of graphs
• Mastermind
• Neighbor-locating coloring: graph operations and extremal cardinalities
• Neighbor-locating colorings in graphs
• On a new class of codes for identifying vertices in graphs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• On the conjectures of neighbor locating coloring of graphs
• On the locating chromatic number of Kneser graphs
• On the locating chromatic number of the Cartesian product of graphs.
• The locating chromatic number of the join of graphs
• The locating-chromatic number for Halin graphs
• The locating-chromatic number of disconnected graphs

Cited in

(3)

• On locating and neighbor-locating colorings of sparse graphs
• Optimal local identifying and local locating-dominating codes
• On the conjectures of neighbor locating coloring of graphs

This page was built for publication: New bounds and constructions for neighbor-locating colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132528)