New bounds and constructions for neighbor-locating colorings of graphs

DOI10.1007/978-3-031-25211-2_9arXiv2301.13557OpenAlexW4318023129MaRDI QIDQ6132528FDOQ6132528

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)

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.

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)

Cites Work

• On a new class of codes for identifying vertices in graphs
• Graphs of order \(n\) with locating-chromatic number \(n-1\)
• The locating chromatic number of the join of graphs
• On the locating chromatic number of the Cartesian product of graphs.
• Title not available (Why is that?)
• The locating-chromatic number for Halin graphs
• Title not available (Why is that?)
• On the locating chromatic number of Kneser graphs
• Title not available (Why is that?)
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Locally identifying coloring of graphs
• Mastermind
• Title not available (Why is that?)
• How complex are random graphs in first order logic?
• Neighbor-locating coloring: graph operations and extremal cardinalities
• Neighbor-locating colorings in graphs
• A Bound for the Locating Chromatic Numbers of Trees
• On the conjectures of neighbor locating coloring of 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)