Injective \(\Delta +2\) coloring of planar graph without short cycles (Q6089365)

This article discusses injective coloring and injective chromatic number of planar graphs with certain degree conditions. Here, \(\Delta\) implies the maximum degree of a vertex of a graph. The concept of the injective chromatic number was introduced by \textit{G. Hahn} et al. [Discrete Math. 256, No. 1--2, 179--192 (2002; Zbl 1007.05046)]. An injective coloring requires that any two vertices get different colors if they have a common neighbor. Let \(G\) be a graph. A vertex \(k\)-coloring is a function \(c: V (G) \to [k]\), with \([k] = \{1, 2, \ldots, k\}\). If its restriction to the neighborhood of any vertex is injective, \(c\) is called an injective coloring. The injective chromatic number \(\chi_i(G)\) of \(G\) is the least integer \(k\) such that \(G\) has an injective \(k\)-coloring. The square of \(G\), also known as the common neighbor graph, denoted as \(G^{(2)} \) is defined as \(V (G^{(2)}) = V (G)\) and \(E(G^{(2)})\) = \(\{[u, v]:\) there is a path of length 2 in \(G\) joining \(u\) and \(v\}\). An injective coloring of \(G\) is just a proper coloring of \(G^{(2)}\), and thus \(\chi_i(G) = \chi(G^{(2)})\). The main focus is on two theorems presented in four sections. Section 1. Introduction: The introduction provides a literature review and introduces three basic theorems related to the ongoing discussions in the field. Section 2. Basic notations: This section explains the necessary definitions frequently used in the paper. Basic notations and definitions related to vertices, forbidden color sets, \(2\)-vertices, \(k\)-vertices, and more are discussed. A \(k\) \((k^+, k^-)\)-vertex refers to a vertex with degree \(k\) (at least \(k\), at most \(k\)). Let \(n_2(v)\) denote the number of \(2\)-vertices in the neighborhood of \(v\), and a \(k(n)\)-vertex refers to a \(k\)-vertex with \(n\) \( 2\)-neighbors. Let \(v\) be a \(k\)-vertex of \(G\) with \(N(v) = \{v_i\mid 1 \le i \le k\}\), and \(d(v_1) \ge d(v_2) \ge \dots \ge d(v_k)\), then the sum of degrees of neighbors of \(v\) is denoted as \(D(v) = \Sigma_{u\in N(v)} d(u)\). A vertex \(v\) is said to be light if \(D(v) \le \Delta + 1 + d(v)\); otherwise, \(v\) is called a heavy vertex. A \(k\)-face \(f \in F(G)\) is denoted by its boundary vertex walk as \(f = [v_1 - v_2 - v_3 - \dots - v_{k-1} - v_k - v_1]\) and a \(k^+\)-face \(f \in F(G)\) is denoted as \(f = [v_1 - v_2 - v_3 - \dots ]\). Section 3. Proof of the first hteorem: This section is devoted to proving the first theorem: Let \(G\) be a planar graph with girth \(g\) and maximum degree \(\Delta\). If \(g \ge 6\) and \(\Delta \ge 7\), then \(\chi_i(G) \le \Delta + 2\). The proof is presented through four lemmas and a corollary. Section 4. Proof of the Second Theorem: The fourth section delves extensively into the proof of the second theorem: Let \(G\) be a planar graph without \(3, 4, 7\)-cycles. If the maximum degree \(\Delta (G) \ge 24\), then \(\chi_i(G) \le \Delta + 2\). This section covers a range of cases and subcases related to the initial charges for vertices and faces. The specific conditions and their corresponding initial charges for vertices are outlined, addressing degrees ranging from 2 to \(\Delta\). Additionally, the paper discusses cases related to faces, specifying the initial charges for faces with degrees 6 and those with degrees greater than or equal to 8. The pattern of the proof involves inspecting the cases of various values of \(n_2(v)\), checking whether a vertex is light or heavy, finding \(D(v)\), considering the presence of 7-cycles, analyzing the existence of 5-faces, identifying bounds for certain parameters like \(tr(u,v)\), \(tr(f,v)\), \(w^{(1)}(v)\), and the initial charge \(w(v)\). The thorough exploration aims to offer a comprehensive understanding of the various scenarios presented in the second theorem's proof. Both theorems heavily rely on the method of contradiction to establish their results. Another distinctive feature of the outcomes is the incorporation of discharging rules into each proof. Each proof involves two sets of distinct discharge rules along with corresponding discharge procedures. Additionally, Euler's formula \(|V (G)|-|E(G)|+|F(G)|=2\) and the handshaking theorem are also utilized at certain points in the proofs. In short, the article systematically explores injective coloring and injective chromatic number of planar graphs.