On the locating chromatic number of the Cartesian product of graphs.

zbMATH Open1413.05100arXiv1106.3453MaRDI QIDQ2828993FDOQ2828993

Authors: Behnaz Omoomi, Ali Behtoei 

Publication date: 26 October 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

Abstract: Let $c$ be a proper $k$-coloring of a connected graph $G$ and $Pi=(C_1,C_2,\mathrm{...},C_k)$ be an ordered partition of $V(G)$ into the resulting color classes. For a vertex $v$ of $G$, the color code of $v$ with respect to $Pi$ is defined to be the ordered $k$-tuple $c_{{}_{P}i}(v):=(d(v,C_1),d(v,C_2),\mathrm{...},d(v,C_k)),$ where $d(v,C_i)=mind(v,x)|xin{C}_i,1leqileqk$. If distinct vertices have distinct color codes, then $c$ is called a locating coloring. The minimum number of colors needed in a locating coloring of $G$ is the locating chromatic number of $G$, denoted by $Cch{i}_{{}_L}(G)$. In this paper, we study the locating chromatic number of grids, the cartesian product of paths and complete graphs, and the cartesian product of two complete graphs.

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

Recommendations

• Locating chromatic number of powers of paths and cycles
• The locating chromatic number of the join of graphs
• Characterizing all trees with locating-chromatic number 3
• Graphs of order \(n\) with locating-chromatic number \(n-1\)
• On the locating chromatic number of Kneser graphs

zbMATH Keywords

Cartesian productlocating chromatic numberlocating coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Cited In (24)

• The locating-chromatic number for Halin graphs
• The locating chromatic number for m-shadow of a connected graph
• The locating chromatic number of the join of graphs
• On some Petersen graphs having locating chromatic number four or five
• Edge-locating coloring of graphs
• On the locating chromatic number of Kneser graphs
• On the comparison of the distinguishing coloring and the locating coloring of graphs
• New bounds and constructions for neighbor-locating colorings of graphs
• Graphs of order \(n\) with locating-chromatic number \(n-1\)
• On locating and neighbor-locating colorings of sparse graphs
• The locating-chromatic number for Corona product of graphs
• Neighbor locating coloring on graphs: three products
• Characterizing all graphs containing cycles with locating-chromatic number 3
• On locating chromatic number of Möbius ladder graphs
• Neighbor-locating coloring: graph operations and extremal cardinalities
• A bound for the locating chromatic number of trees
• The locating-chromatic number of firecracker graphs
• Local connective chromatic number of Cartesian product of some graphs
• On the conjectures of neighbor locating coloring of graphs
• On locating-chromatic number of complete \(n\)-ary tree
• On ( k , ℓ )-locating colorings of graphs
• Neighbor-locating colorings in graphs
• On the locating-chromatic numbers of subdivisions of friendship graph
• Upper bounds of the locating chromatic numbers of shadow cycle graphs

This page was built for publication: On the locating chromatic number of the Cartesian product of graphs.

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