Recognizable coloring of graphs
Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Chemical graph theory (05C92) Approximation methods and heuristics in mathematical programming (90C59) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)
The paper Recognizable Coloring of Graphs studies a vertex coloring concept called recognizable coloring in graph theory. In this type of coloring, each vertex in a graph must be uniquely identifiable based on its color code, which depends on the color assigned to the vertex and the distribution of colors among its neighbors.\N\NThe authors focus mainly on determining the recognition number of graphs obtained through specific graph operations, particularly (i) the corona product of graphs and (ii) the edge corona product of graphs. The paper establishes theoretical results for the recognition numbers of these graph constructions when the second graph involved is a complete graph \(K_n\). It also proposes a Local Search Algorithm (LSA) for computing recognizable colorings and demonstrates the application of this algorithm on fullerene graphs, which are structures used in chemical graph theory.\N\NThe paper is divided into five parts: (i) Introduction, (ii) Recognizable Coloring of Corona Products, (iii) Recognizable Coloring of Edge Corona Products, (iv) Finding a Recognizable Coloring of a Graph Using a Local Search Algorithm, and (v) Experimental Results.\N\NRecognizable coloring is related to several known coloring concepts, such as: (i) irregular coloring, (ii) vertex-distinguishing coloring, (iii) neighbor-distinguishing coloring. In recognizable coloring, the focus is not only on assigning colors but also on ensuring that each vertex can be uniquely recognized using its color code. That is, the color code of a vertex includes: (i) the color assigned to the vertex, (ii) the number of neighbors of each color. If every vertex has a unique color code, the coloring is called a recognizable coloring. The formal definition is as follows: Let \(f\) be a mapping from \(V(G)\) to \(S\), where \(G\) is a connected graph and \(S\) is a set of \(k\) colors for a positive integer \(k\). The ordered \((k+1)\)-tuple \((x_0, x_1, \ldots, x_k)\) is the color code of a vertex \(v\) of \(G\) with respect to \(f\), represented by \(\text{code}_G(v \mid f)\), \(x_0\) is the color assigned to \(v\), and \(x_i\) is the number of vertices adjacent to \(v\) of color \(i\) for \(1 \leq i \leq k\). In other words, \(x_i = |\{uv \in E(G) : f(u) = i\}|\) for \(1 \leq i \leq k\). If \(\text{code}_G(u \mid f) \neq \text{code}_G(v \mid f)\) for each pair of distinct vertices \(u\) and \(v\) of \(G\), then the mapping \(f\) is a recognizable coloring. The minimum number of colors needed for a recognizable coloring of \(G\) is the recognition number of \(G\), denoted by \(rn(G)\).\N\NLet \(G\) and \(H\) be two graphs with \(V(G) = \{g_1, \ldots, g_m\}\), \(E(G) = \{e_1, \ldots, e_m\}\) and let \(H_1, \ldots, H_m\) be \(m\) vertex-disjoint copies of \(H\). The corona product \(G \circ H\) of \(G\) and \(H\) is obtained by taking one copy of \(G\) and the \(m\) copies of \(H\) and joining by an edge the vertex \(g_i\) of \(G\) to every vertex in the \(i\)th copy \(H_i\) of \(H\) for \(i = 1,2, \ldots, m\). The edge corona product \(G \diamond H\) of \(G\) and \(H\) is obtained from one copy of \(G\) and \(m\) copies of \(H\) as follows: for each edge \(e_i = g_i g'_i\) of \(G\), we join \(g_i\) and \(g'_i\) to every vertex in the \(i\)th copy \(H_i\) of \(H\) associated with the edge \(e_i\) for \(i = 1,2, \ldots, m\). The \(i\)th copy \(H_i\) of \(H\) corresponding to the edge \(e_i\) of \(G\) is also denoted by \(H_{e_i}\) for \(i = 1,2, \ldots, m\). A fullerene graph is a planar 3-connected cubic graph whose faces are pentagons and hexagons.\N\NThe results given in the paper are:\N\begin{itemize}\N\N\item Lemma: Let \(G\) be a graph of order \(m\) and let \(H = K_n\). If \(f\) is a recognizable coloring of \(G \circ H\), then \(f(u) \neq f(v)\) for every two distinct vertices \(u\) and \(v\) in the \(i\)th copy of \(H\) for all \(i = 1,2, \ldots, m\).\N\N\item Theorem: Let \(G\) and \(H\) be two graphs of order \(m\) and \(n\), respectively. If \(1 < m \le n\), then \( rn(G \circ H) \le n.\)\N\N\item Corollary: If \(G\) is a graph of order \(m\), then \( rn(G \circ K_n) = n\) where \(1 < m \le n\).\N\N\item Theorem: For \(m > n\), \( rn(K_m \circ K_n) = \min \left\{ t : m \le \binom{t}{n+1} + n \binom{t}{n} \right\}. \)\N\N\item Theorem: Let \(H\) be a graph and \( \rho = \max \{ m, d_{H1}, \dots, d_{H\Delta_H} \}\) where \(m > 1\) and \( d_{Hi} = |\{ u \in V(H) : \deg_H(u) = i \}| \) for \(i = 1,2, \ldots, \Delta_H\). Then \( rn(K_m \circ H) \le \rho.\)\N\N\item Lemma: Let \(G\) be a graph of size \(m\) and let \(H = K_n\). If \(f\) is a recognizable coloring of \(G \diamond H\), then \( f(u) \neq f(v) \) for every two distinct vertices \(u\) and \(v\) in the \(i\)th copy of \(H\) for all \(i = 1,2, \ldots, m\).\N\N\item Theorem: If \(G\) is a connected graph of order \(p\) and size \(m\) where \(m \ge p\), then \( rn(G \diamond K_n) = n\) where \(n \ge m\).\N\N\item Proposition: \( rn(G \diamond K_n) \ge \min \left\{ t : m \le \binom{t}{n+2} + (n+1)\binom{t}{n+1} + \frac{n(n+1)}{2}\binom{t}{n} \right\}.\)\N\N\item The algorithm works as follows:\N\N1. Start with an initial random coloring.\N\N2. Compute color codes of all vertices.\N\N3. Detect conflicts (vertices having identical color codes).\N\N4. Modify the coloring by changing the color of selected vertices.\N\N5. Repeat until all vertices have unique color codes or a stopping condition is reached.\N\N\end{itemize}\N\NThe paper mainly uses the following methods of proof: (i) the contradiction method, (ii) constructive coloring arguments, (iii) the combinatorial counting methods, and (iv) the case analysis. Though the algorithm provides a computational method to find recognizable colorings for complex graphs, the computational complexity is not fully discussed. Even then, the paper presents valuable theoretical results on recognizable coloring and extends the understanding of recognition numbers in graph products. The combination of mathematical analysis and algorithmic development makes the work both theoretically interesting and computationally relevant.
- Dominated and dominator colorings over (edge) corona and hierarchical products
- Domination in Graphs: Core Concepts
- scientific article; zbMATH DE number 5128956 (Why is no real title available?)
- scientific article; zbMATH DE number 3895095 (Why is no real title available?)
- Recognizable colorings of cycles and trees
- Recognizable colorings of graphs
- The spectrum of the edge corona of two graphs
This page was built for publication: Recognizable coloring of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6892108)
