
An injective coloring of a graph G is a vertex coloring such that a pair of vertices obtain distinct colors if there is a path of length two between them. It is proved in this paper that χli(G)≤Δ+4 if Δ≥12 when G does not have a 4−-cycle intersecting with a 5−-cycle. Our result improves a previous result of Cai et al. in 2023, who showed that χli(G)≤Δ+4 when Δ≥12 and G has disjoint 5−-cycles.
Citation: Yuehua Bu, Hongrui Zheng, Hongguo Zhu. On the list injective coloring of planar graphs without a 4−-cycle intersecting with a 5−-cycle[J]. AIMS Mathematics, 2025, 10(1): 1814-1825. doi: 10.3934/math.2025083
[1] | Hongyu Chen, Li Zhang . A smaller upper bound for the list injective chromatic number of planar graphs. AIMS Mathematics, 2025, 10(1): 289-310. doi: 10.3934/math.2025014 |
[2] | Yanping Yang, Yang Wang, Juan Liu . List vertex arboricity of planar graphs without 5-cycles intersecting with 6-cycles. AIMS Mathematics, 2021, 6(9): 9757-9769. doi: 10.3934/math.2021567 |
[3] | Fugang Chao, Donghan Zhang . Neighbor sum distinguishing total choice number of IC-planar graphs with restrictive conditions. AIMS Mathematics, 2023, 8(6): 13637-13646. doi: 10.3934/math.2023692 |
[4] | Yuehua Bu, Qi Jia, Hongguo Zhu, Junlei Zhu . Acyclic edge coloring of planar graphs. AIMS Mathematics, 2022, 7(6): 10828-10841. doi: 10.3934/math.2022605 |
[5] | Yueying Zhao, Lianying Miao . Planar graphs without {4,6,8}-cycles are 3-choosable. AIMS Mathematics, 2021, 6(9): 10253-10265. doi: 10.3934/math.2021593 |
[6] | Yuehua Bu, Qiang Yang, Junlei Zhu, Hongguo Zhu . Injective coloring of planar graphs with girth 5. AIMS Mathematics, 2023, 8(7): 17081-17090. doi: 10.3934/math.2023872 |
[7] | Yanyi Li, Lily Chen . Injective edge coloring of generalized Petersen graphs. AIMS Mathematics, 2021, 6(8): 7929-7943. doi: 10.3934/math.2021460 |
[8] | Xiaoxue Hu, Jiangxu Kong . An improved upper bound for the dynamic list coloring of 1-planar graphs. AIMS Mathematics, 2022, 7(5): 7337-7348. doi: 10.3934/math.2022409 |
[9] | Yunfeng Tang, Huixin Yin, Miaomiao Han . Star edge coloring of K2,t-free planar graphs. AIMS Mathematics, 2023, 8(6): 13154-13161. doi: 10.3934/math.2023664 |
[10] | Jin Cai, Shuangliang Tian, Lizhen Peng . On star and acyclic coloring of generalized lexicographic product of graphs. AIMS Mathematics, 2022, 7(8): 14270-14281. doi: 10.3934/math.2022786 |
An injective coloring of a graph G is a vertex coloring such that a pair of vertices obtain distinct colors if there is a path of length two between them. It is proved in this paper that χli(G)≤Δ+4 if Δ≥12 when G does not have a 4−-cycle intersecting with a 5−-cycle. Our result improves a previous result of Cai et al. in 2023, who showed that χli(G)≤Δ+4 when Δ≥12 and G has disjoint 5−-cycles.
Let G be a finite, simple, and planar graphs throughout this paper. A 2-distance k-coloring of G is a mapping c:V(G)→{1,2,⋯,k} such that the vertices whose distance is at most two receive distinct colors. The 2-distance chromatic number is the least integer k such that G has a 2-distance k-coloring, denoted by χ2(G). In 1977, Wegner [15] first defined the 2-distance coloring and proposed the following conjecture:
Conjecture 1.1. Let G be a planar graph with maximum degree Δ. Then
χ2(G)≤{7ifΔ=3;Δ+5if4≤Δ≤7;⌊3Δ2⌋+1ifΔ≥8. |
Recently, Kim and Lian [10] showed that each subcubic planar graph G has χ2(G)≤7 if g(G)≥6. Then Yu et al. [16] proved that every planar graph G has χ2(G)≤18 if Δ≤5, and χ2(G)≤4Δ−3 if Δ≥6.
An injective k-coloring of G is a mapping c:V(G)→{1,2,⋯,k} such that c(u)≠c(v) if there is a path of length two between u and v. The injective chromatic number of G is the smallest positive integer k such that G is injectively k-colorable, denoted by χi(G). So it is clear that χi(G)≤χ2(G). Give a list assignment, L={L(v):v∈V(G)}. A list injective coloring of G is an injective coloring of G such that c(v)∈L(v) for each vertex v∈G. An injective L-coloring is an injective coloring such that c(v)∈L(v) for any vertex v of G. Moreover, G is injectively k-choosable if G has an injective L-coloring for any L with |L(v)|≥k. The injective choosability number of G is the smallest positive integer k such that G is injectively k-choosable, denoted by χli(G).
In 2002, Hahn et al. [9] first defined the concept of injective coloring, and they applied it to the theory of error-correcting codes. If the injective chromatic number of the hypercube Qn had been shown to be exponential in n, then there would have been consequences for some complexity concerns on random access machines. They gave a slightly smaller upper bound: χi(G)≤Δ2−Δ+1. The upper bound is strengthened to χi(G)≤Δ2−Δ if Δ≥3 by Chen et al. [7]. In 2010, Lužar [12] gave the following conjecture by studying Conjecture 1.1:
Conjecture 1.2. Let G be a planar graph with maximum degree Δ.
χi(G)≤{5ifΔ=3;Δ+5if4≤Δ≤7;⌊3Δ2⌋+1ifΔ≥8. |
Many researchers have done many studies on this conjecture. For every K4-minor-free graph G, Chen et al. [7] showed χi(G)≤⌈32Δ⌉. They conjectured χi(G)≤⌈32Δ⌉ for every planar graph G, but Lužar and Škrekovski [13] proved it was wrong.
Also, there are many results about planar graph G with girth restrictions.
Theorem 1.3. (Lužar et al. [14]) Let G be a planar graph and Δ≤3.
(1) If g(G)≥19, then χi(G)≤3;
(2) If g(G)≥10, then χi(G)≤4;
(3) If g(G)≥7, then χi(G)≤5.
Theorem 1.4. Suppose that planar graph G has g(G)≥6.
(1) [6] χli(G)≤Δ+3;
(2) [3] If Δ≥8, then χli(G)≤Δ+2;
(3) [1] If Δ≥24, then χli(G)≤Δ+1.
Theorem 1.5. Suppose that planar graph G has g(G)≥5.
(1) [5] χli(G)≤Δ+6;
(2) [2] If Δ≥11, then χli(G)≤Δ+4;
(3) [8] If Δ≥2339, then χi(G)≤Δ+1.
More recently, Li et al. [11] proved that if G is a planar graph with Δ≥22 that has no intersecting 4-cycles or triangles, then χli(G)≤Δ+4. Cai et al. [4] showed that χli(G)≤Δ+4 if G is a planar graph with Δ≥12 that has disjoint 5−-cycles. We strengthen the result of Cai et al. [4] and allow that G has 5-cycles intersecting 5-cycles by proving Theorem 1.6.
Theorem 1.6. If G is a planar graph with Δ≥12 that has no 4−-cycles intersecting with 5−-cycles, then χli(G)≤Δ+4.
We define N(v)={v1,v2,⋯,vk} and D(v)=∑1≤i≤kd(vi) for a k-vertex v. The number of k-neighbors of v is denoted by nk(v). For a 2+-vetex v, if D(v)≥Δ+4+d(v), then v is called a heavy vertex; otherwise, v is called a light vertex. A k(l)-vertex is a k-vertex that has l 2-neighbors. For a path xwy, if d(w)=2, then we say x and y are fake-adjacent. The number of k-faces that are incident with v, denoted mk(v). We say that 2-vertex v is of Classone(resp., Classtwo, Classthree, Classfour, Classfive) if m3(v)=1(resp., m4(v)=1, m5(v)=2, m5(v)=m6+(v)=1, m6+(v)=2). If a 3(1)-vertex w has a Class one 2-neighbor, then w is called a strong 3(1)-vertex; otherwise, w is called a weak 3(1)-vertex. The number of strong 3(1)-neighbors of w is denoted by nst(w). For k-vertex v, we define f1,f2,⋯,fk as being incident with v. If two cycles have a common vertex, then we say they are intersecting with each other.
Observation. If v is a Class one 2-vertex, then m7+(v)=1; if v is a Class two 2-vertex, then m6+(v)=1.
With the intention of proving Theorem 1.6, we suppose instead that G is a counterexample with the fewest edges, which indicates that χli(G)>Δ+4 and χli(H)≤Δ+4 for any H⊂G. For a partial vertex coloring c of G and each vertex v, the forbidden color set is denoted by F(v), and L denotes an arbitrary list assignment with |L(v)|≥Δ+4.
Lemma 2.1. There are no adjacent light vertices.
Proof. Suppose that u and v are distinct light vertices and uv∈E(G). By G having the fewest edges, G−uv is injective L-choosable. Decolor u and v. Clearly, |F(v)|≤D(u)−d(u)≤Δ+3 and |F(u)|≤D(u)−d(u)≤Δ+3. So recolor u and v by c(u)∈L(u)−F(u) and c(v)∈L(v)−F(v). Then G has an injective L-coloring, a contradiction.
It is easy to know the following corollaries from Lemma 2.1.
Corollary 2.2. There are no adjacent 2-vertices, and δ(G)≥2.
Corollary 2.3. Suppose 3≤d(v)≤5. If n2(v)≥1, then v is a heavy vertex and n2(v)≤d(v)−2.
Lemma 2.4. Let v be a 3(1)-vertex and u be a 5-vertex. If n2(u)≥1, then uv∉E(G).
Proof. Assume the assertion of the lemma is false that u is adjacent to v. Suppose that v1 is the 2-neighbor of v and u1 is the 2-neighbor of u. By the choice of G, G−vv1 is injective L-choosable. Remove the colors of v, u1, and v1. Clearly, |F(v)|≤Δ+3. Note that v1 and u1 are light vertices, which indicates that |F(v1)|≤D(v1)−d(v1)≤Δ+3 and |F(u1)|≤D(u1)−d(u1)≤Δ+3. Thereby, we recolor v, u1, and v1 in sequence, a contradiction.
Lemma 2.5. Suppose that d(v)=6 and v1 is a 2-neighbor of v. If m4(v1)=1, then v is a heavy vertex.
Proof. Assume to the contrary that v is a light vertex. By G having the fewest edges, G−vv1 has an injective L-coloring. Decolor v and v1. Clearly, |F(v1)|≤5+Δ−2=Δ+3. Since v is a light vertex, we have |F(v)|≤D(v)−d(v)≤Δ+3. So we can recolor v1 and v in sequence, a contradiction.
Lemma 2.6. Let f=[v′1v1vv2v′2] be a 5-face with d(v)=6, d(v1)=d(v′2)=2, and d(v2)=3. Then v is a heavy vertex.
Proof. Assume to the contrary that v is a light vertex. Clearly, G−vv1 has an injective L-coloring. Decolor v, v1, and v′2. Clearly, |F(v1)|≤d(v)−1+Δ−2=Δ+3. It follows from v and v′2 being light vertices that we can recolor v1, v, and v′2 in sequence, a contradiction.
Lemma 2.7. Let v be a 3(1)-vertex. If v1 is a Class one 2-neighbor, then D(v)≥Δ+8.
Proof. Suppose to the contrary that D(v)≤Δ+7. By Corollary 2.3, we need to consider that D(v)=Δ+7. It follows from G having the fewest edges that G−vv1 has an injective L-coloring. Decolor v and v1. Obviously, |F(v)|≤D(v)−d(v)−1≤Δ+3. Notice that v1 is a light vertex. So, we recolor v and v1 in sequence, a contradiction.
Note that G has no 4−-cycles intersect with 5−-cycles. According to Euler's formula |V(G)|+|F(G)|−|E(G)|=2, and ∑v∈V(G)d(v)=∑f∈F(G)d(f)=2|E(G)|, we derive the following equation:
∑v∈V(G)(d(v)−6)+∑f∈F(G)(2d(f)−6)=−12. |
Then we construct the weight function ω(v)=d(v)−6 for each v∈V(G) and ω(f)=2d(f)−6 for each f∈F(G), which means that ∑x∈V(G)⋃F(G)ω(x)=−12. In this section, we get a new weight function ω′(x) by assigning the weight. Thereby, we have the following contradiction:
0≤∑x∈V(G)⋃F(G)ω′(x)=∑x∈V(G)⋃F(G)ω(x)=−12. |
It shows that G does not exist, so Theorem 1.6 is proved. Then τ(u→v) shows the weight that u transfers to v, and τ(u→f→v) denotes the weight that u transfers to v by f, where u,v∈V(G) and f∈F(G). Next, we introduce two face types of configurationA and configurationB. We define the number of configuration A-face(resp., B-face) contain v as mA(v)(resp., mB(v)).
configurationA-face: Suppose f=[v′1v1vv2v′2] with 6≤d(v)≤8, 2≤d(vi)≤3, and d(v′i)≥10(i=1,2) (See Figure 1(a)). configurationB-face: Suppose f=[v′1v1vv2v′2] with d(v)=9, d(vi)=2 and d(v′i)≥9(i=1,2) (See Figure 1(b)).
The discharging rules
R1 Let f be a 4+-face. Then τ(f→incidentvertices)=2−6d(f).
R2 Let uv∈E(G) and d(u)≥3. If v is a Class one(resp., Class two, Class three, Class four, Class five) 2-vertex, then τ(u→v)=107(resp.,54,65,1110,1).
R3 Let d(v)=3 and uv∈E(G).
R3.1 Suppose that v is a light 3(0)-vertex and u is a heavy vertex with 3≤d(u)≤7. Then τ(u→v)=13.
R3.2 Suppose that v is a heavy 3(0)-vertex. If d(u)=4(resp., 5≤d(u)≤7), then τ(u→v)=130(resp., 13).
R3.3 Suppose that v is a weak 3(1)-vertex. Assume m3(v)=1, if d(u)=5(resp., 6, 7, 8, 9), then τ(u→v)=710(resp.,34,45,910,1110). Assume m4+(v)=3, if d(u)=5(resp., 6, 7, 8, 9), then τ(u→v)=12(resp.,1120,35,910,1).
R3.4 Suppose that v is a strong 3(1)-vertex. If d(u)=6(resp.,7,8,9), then τ(u→v)=78(resp.,1213,1,87). If d(u)≥10, then τ(u→v)=2−7d(u).
R4 Let d(v)=4 and uv∈E(G). If d(u)=5(resp., 6≤d(u)≤7), then τ(u→v)=130(resp., 27).
R5 Suppose 8≤d(u)≤9 such that uv∈E(G).
R5.1 If d(v)=3,4 except for 3(1)-vertex, then τ(u→v)=910 when d(u)=8 and τ(u→v)=1 when d(u)=9.
R5.2 If d(v)=5, then τ(u→v)=35.
R5.3 If d(v)=6, then τ(u→v)=35 when d(u)=9.
R6 Suppose 3≤d(v)≤8 except for strong 3(1)-vertex. If d(u)≥10 such that uv∈E(G), then τ(u→v)=95−6d(u)≥65.
R7 Let d(u)≥10 and 6≤d(v)≤8. If u is fake-adjacent to v by a Class five 2-vertex, then τ(u→v)=45−6d(u).
R8 Suppose f=[v′1v1vv2v′2]. After R1∼R6, the 9-vertex v is called big 9-vertex if ω′(v)<0.
R8.1 If f is a configuration A-face, then τ(v′i→f)=910−3d(v′i)(i=1,2) through v′1v′2 and τ(f→v)≥95−6min{d(v′1),d(v′2)} (See Figure 1(a)).
R8.2 If v is a big vertex and f is a configuration B-face, then τ(v′i→f)=310 through v′1v′2 and f transfers 35 to each big 9-vertex equally (See Figure 1(b)).
Firstly, we check ω′(v) for each v∈V(G).
Case 1. d(v)=2 and then ω(v)=−4.
If v is a Class one 2-vertex, then m3(v)=m7+(v)=1, which means that 2∑i=1τ(fi→v)≥87 by R1. Hence, ω′(v)≥−4+87+107×2=0 by R2. If v is a Class two 2-vertex, then m4(v)=m6+(v)=1, which indicates that 2∑i=1τ(fi→v)≥12+1=32 by R1. So ω′(v)≥−4+32+54×2=0 by R2. Next, consider that v is a Class three, Class four, or Class five 2-vertex. It resembles the above arguments that can be obtained that ω′(v)≥−4+min{65×2+45×2,1110×2+45+1,2+2}=0 by R1, R2.
Case 2. d(v)=3 and then ω(v)=−3. Let N(v)={v1,v2,v3} with d(v1)≤d(v2)≤d(v3).
Subcase 2.1. Suppose n2(v)=0. If m4−(v)=1, then m6+(v)=2; otherwise, m5+(v)=3. Then 3∑i=1τ(fi→v)≥min{2,45×3}=2 by R1. Consider that v is a light vertex, which means that vi(i=1,2,3) are heavy vertices by Lemma 2.1. According to R3.1, R5.1, R6, 3∑i=1τ(vi→v)≥13×3=1. Then ω′(v)≥−3+2+1=0. Otherwise, consider that v is a heavy vertex. Suppose n3(v)=0. If n4(v)=0, then n5+(v)=3; if n4(v)≥1, then either n9+(v)≥1 or n7(v)=n8(v)=1, which means that 3∑i=1τ(vi→v)≥min{13×3,130+1,130+13+910}=1 by R3.2, R5.1, R6. Hence, ω′(v)≥−3+2+1=0. Suppose d(v1)=3, which indicates that τ(v→v1)≤13 by R3.1. If d(v2)=4, then d(v3)≥12; if 5≤d(v2)≤7, then d(v3)≥9; otherwise, d(v2),d(v3)≥8. So 3∑i=2τ(vi→v)≥min{130+(95−612),13+1,910×2}=43 by R3.2, R5.1, R6. Furthermore, ω′(v)≥−3+2−13+43=0.
Subcase 2.2. Suppose d(v1)=2. By Corollary 2.3, d(v2)+d(v3)≥Δ+5. Consider that v is a weak 3(1)-vertex. Suppose m3(v)=1. If d(v2)=5, then d(v3)≥12; if d(v2)=6, then d(v3)≥11; if d(v2)=7, then d(v3)≥10; otherwise, d(v2)≥8 and d(v3)≥9. Therefore, 3∑i=2τ(vi→v)≥min{710+(95−612),34+(95−611),45+(95−610),910+1110}=2 by R3.3, R5, R6. Thereby, ω′(v)≥−3+2−1+2=0 by R1, R2. If m4+(v)=3, then −τ(v→v1)+3∑i=1τ(fi→v)≥min{−54+12+2,−65+45×3}=65 by R1, R2. So ω′(v)≥−3+65+min{12+(95−612),1120+(95−611),35+(95−610),910+1}=0 by R3.3, R6. Next, consider that v is a strong 3(1)-vertex. By Lemma 2.7, d(v2)+d(v3)≥Δ+6. Moreover, −τ(v→v1)+3∑i=1τ(fi→v)≥−107+87+1=57 by R1, R2. Thus, ω′(v)≥−3+57+min{78+(2−712),1213+(2−711),1+(2−710),87+87}=0 by R3.4.
Case 3. d(v)=4 and then ω(v)=−2. Let N(v)={v1,v2,v3,v4} with d(v1)≤d(v2)≤d(v3)≤d(v4).
Subcase 3.1. Suppose n2(v)=0. If m4−(v)=1, then m6+(v)=3; otherwise, m5+(v)=4. So 4∑i=1τ(fi→v)≥min{3,45×4}=3 by R1. If v is a heavy vertex, then n3(v)≤3. Note that n11+(v)≥1 if n3(v)=3. Therefore, −τ(v→3-neighbors)+τ(11+-neighbor→v)≥min{−13×3+(95−611),−13×2}=−23 by R3.1, R6. Hence, ω′(v)≥−2+3−23=13. Otherwise, suppose that v is a light vertex, which implies that vi(1≤i≤4) are not light 3-vertices by Lemma 2.1. Clearly, ω′(v)≥−2+3−130×4=1315 by R3.2.
Subcase 3.2. Suppose d(v1)=2. By Corollary 2.3, d(v2)+d(v3)+d(v4)≥Δ+6. According to R1, R2, if v1 is a Class one 2-vertex, then −τ(v→v1)+4∑i=1τ(fi→v)≥−107+87+2=127; if v1 is a Class two 2-vertex, then −τ(v→v1)+4∑i=1τ(fi→v)≥−54+12+3=94; if m5+(v)=4, then −τ(v→v1)+4∑i=1τ(fi→v)≥−65+45×4=2; otherwise m6+(v1)=2 and m4−(v)=1, then −τ(v→v1)+4∑i=1τ(fi→v)≥−1+3=2. Therefore, −τ(v→v1)+4∑i=1τ(fi→v)≥min{127,94,2,2}=127. If n3(v)=0, then n6+(v)≥1; if n3(v)=1, then n8+(v)≥1; if n3(v)=2, then n12+(v)=1. This implies that −τ(v→3-neighbors)+τ(6+-neighbors→v)≥min{27,−13+910,−13×2+(95−612)}=27 by R3.1, R4, R5.1, R6. Moreover, ω′(v)≥−2+127+27=0.
Subcase 3.3. Suppose d(v1)=d(v2)=2, which means that d(v3)+d(v4)≥Δ+4 by Corollary 2.3. According to R1, R2, −τ(v→v1)−τ(v→v2)+4∑i=1τ(fi→v)≥min{−107−1+87+2,−54×2+12+3,−65×2+45×4,−2+3}=57. If d(v3)=4, then d(v4)≥12; if d(v3)=5, then d(v4)≥11; if 6≤d(v3)≤7, then d(v4)≥9; otherwise, d(v3),d(v4)≥8. This indicates that 4∑i=3τ(vi→v)≥min{95−612,130+(95−611),27+1,910×2}=97 by R4, R5.1, R6. So ω′(v)≥−2+57+97=0.
Claim 3.1. Let 5≤d(v)≤7. Note that v is adjacent to at most one weak 3(1)-vertex that is incident with a 3-face.
Case 4. d(v)=5 and then ω(v)=−1.
Subcase 4.1. Suppose n2(v)=0. According to R1, 5∑i=1τ(fi→v)≥min{4,4+12,45×5}=4. Therefore, ω′(v)≥−1+4−710−12×4=310 by R3.3 and Claim 3.1. Suppose n2(v)=1, which implies that v is a heavy vertex by Corollary 2.3 and n3(1)(v)=0 by Lemma 2.4. Then n3(v)+n4(v)≤3. According to R1, R2, −τ(v→2-neighbor)+5∑i=1τ(fi→v)≥min{−107+87+3,−54+12+4,−65+45×5,−1+4}=197. Note that n10+(v)=1 if n3(v)=3. Therefore, −τ(v→3-neighbors)−τ(v→4-neighbors)+τ(10+-neighbors→v)≥min{−13×3+(95−610),−13×2−130×2}=−1115 by R3.1, R3.2, R4, R6. Hence, ω′(v)≥−1+197−1115=103105.
Subcase 4.2. Suppose n2(v)=2. This implies that v is a heavy vertex by Corollary 2.3, and n3(1)(v)=0 by Lemma 2.4. Then n3(v)+n4(v)≤2. According to R1, R2, −τ(v→2-neighbors)+5∑i=1τ(fi→v)≥min{−107−1+87+3,−54×2+12+4,−65×2+45×5,−2+4}=85. Note that n11+(v)=1 if n3(v)=2. Moreover, −τ(v→3-neighbors)−τ(v→4-neighbors)+τ(11+-neighbor→v)≥min{−13×2+(95−611),−13−130×2}=−25 by R3.1, R4, R6. Thus, ω′(v)≥−1+85−25=15. Suppose n2(v)=3, which means that v is a heavy vertex by Corollary 2.3, and n3(1)(v)=0 by Lemma 2.4. Then n3(v)+n4(v)≤1. Clearly, −τ(v→2-neighbors)+5∑i=1τ(fi→v)≥min{−107−2+87+3,−54×2−1+12+4,−65×3+45×5,−3+4}=25 by R1, R2. If n3(v)=n4(v)=0, then n8+(v)≥1; if n3(v)=1, then n12+(v)=1; if n4(v)=1, then n11+(v)=1. Moreover, ω′(v)≥−1+25+min{35,−13+(95−612),−130+(95−611)}=0 by R3.1, R4, R5.2, R6.
Claim 3.2. Suppose d(v)≥6, m5+(v)=d(v), and nst(v)=t. If 1≤t≤d(v)−1, then m6+(v)≥t+1, w.l.o.g., m6+(v)≥t for t≥0.
Case 5. d(v)=6 and then ω(v)=0.
Claim 3.3. Consider that v is a light vertex. Suppose that w is a 2-neighbor of v and u is a 3(1)-neighbor of v. Then m4−(w)=0 and uv is not incident with 3-face. If v is incident with a configuration A-face f contains 2-neighbors and 3(1)-neighbor of v, then τ(f→v)≥6955.
Proof. By Lemma 2.5, m4(w)=0. If m3(w)=1, then there is a Δ-vertex in N(v) by Lemma 2.1, which means v is a heavy vertex, a contradiction. Suppose that uv is incident with 3-face. Then there is a (Δ−1)+-vertex in N(v), which implies that v is a heavy vertex, a contradiction. Next, consider that v is incident with the configuration A-face f and f is incident with a 2-neighbor and a 3(1)-neighbor of v. By R8.1, it is easy to know that τ(f→v)≥95−611=6955.
Subcase 5.1. Suppose n2(v)=0. If v is a heavy vertex, then n3(v)≤5. According to R1, 6∑i=1τ(fi→v)≥min{45×6,5}=245. Therefore, ω′(v)≥245−5×78−27=39280 by R3.4, R4. Otherwise, consider that v is a light vertex. If m4−(v)=1, then nst(v)≤4 by Claim 3.2. Then ω′(v)≥5−4×78−34−1120=15 by R1, R3.3, R3.4 and Claim 3.1. Consider that m5+(v)=6. If nst(v)≤4, then ω′(v)≥45×6−4×78−1120×2=15 by R1, R3.3, R3.4. If nst(v)≥5, then m6+(v)=6 by Claim 3.2. It follows that ω′(v)≥6−6×78=34 by R1, R3.4.
Subcase 5.2. Suppose n2(v)=1. If v is a heavy vertex, then either n3(v)+n4(v)≤4 or n4(v)=5, which derives that τ(v→3-neighbors)+τ(v→4-neighbors)≤max{78×4,27×5}=72 by R3.4, R4. According to R1, R2, −τ(v→2-neighbor)+6∑i=1τ(fi→v)≥min{−107+87+4,−54+12+5,−65+45×6,−1+5}=185. Therefore, ω′(v)≥185−72=110. Consider that v is a light vertex. If m4−(v)=1, then nst(v)≤3 by Claim 3.2 and Claim 3.3, and τ(v→2-neighbor)=1 by R2 and Claim 3.3. So ω′(v)≥−1+5−78×3−34−1120=340 by R1, R3.3, R3.4, and Claim 3.1. Consider that m5+(v)=6. Suppose nst(v)=t≤5. Then −τ(v→2-neighbor)+6∑i=1τ(fi→v)≥−65+t+45(6−t)=15t+185 by R1, R2 and Claim 3.2. Thereby, ω′(v)≥15t+185−78t−1120(5−t)=−18t+1720≥940 by R3.3, R3.4.
Subcase 5.3. Suppose n2(v)=2. If v is a heavy vertex, then n3(v)+n4(v)≤3. According to R1, R2, −τ(v→2-neighbors)+6∑i=1τ(fi→v)≥min{−107−1+87+4,−54×2+12+5,−65×2+45×6,−2+5}=125. Note that n9+(v)=1 if n3(v)=3. Clearly, ω′(v)≥125+min{−78×3+35,−78×2−27}=51140 by R3.4, R4, R5.3. Otherwise, consider that v is a light vertex. By Claim 3.3 and R2, τ(v→2-neighbors)=2. If m3(v)=1, then n3(1)(v)≤2 by Claim 3.3. Then ω′(v)≥5−2−78×2−13×2=712 by R1, R2, R3.2, R3.4. If m4(v)=1, then nst(v)≤2 by Claim 3.2 and Claim 3.3. Obviously, ω′(v)≥−2+5+12−78×2−1120×2=1320 by R1, R2, R3.3, R3.4, and Claim 3.1. Finally, consider that m5+(v)=6. Suppose nst(v)=t≤4. If t=0, then ω′(v)≥−65×2+45×6−1120×4=15 by R1, R2, R3.3; if 1≤t≤3, then ω′(v)≥−65×2+t+1+45(5−t)−78t−1120(4−t)=−18t+25≥140 by R1, R2, R3.3, R3.4 and Claim 3.2; if t=4, then m6+(v)≥5 and v has two 2-neighbors of Class four or Class five. Moreover, ω′(v)≥min{−1110,−1}×2+5+45−78×4=110 by R1, R2, R3.4.
Subcase 5.4. Suppose n2(v)=3. If v is a heavy vertex, then n3(v)+n4(v)≤2. Clearly, n10+(v)=1 if n3(v)=2. Hence, ω′(v)≥−65×3+45×6+min{−78×2+(95−610),−78−27}=11280 by R1, R2, R3.4, R4, R6. Otherwise, consider that v is a light vertex. If m3(v)=1, then n3(1)(v)≤1 by Claim 3.3. Then ω′(v)≥5−3−78−2×13=1124 by R1, R2, R3.2, R3.4 and Claim 3.3. If m4(v)=1, then nst(v)≤1 by Claim 3.2 and Claim 3.3. So ω′(v)≥5+12−3−78−1120×2=2140 by R1, R2, R3.3, R3.4, and Claim 3.3. Consider that m5+(v)=6. Suppose nst(v)=t≤3. If mA(v)≥1, then ω′(v)≥−65×3+t+45(6−t)+6955−78t−1120(3−t)=−18t+177220≥189440 by R1, R2, R3.3, R3.4, Claim 3.2 and Claim 3.3. Consider that mA(v)=0. Suppose nst(v)=0. If n3(1)(v)=0, then ω′(v)≥−65×3+45×6−13×3=15 by R1, R2, R3.2. If n3(1)(v)≥1, then m6+(v)≥2 and v has at least two 2-neighbors of Class four or Class five by Lemma 2.6. Hence, ω′(v)≥−65−1110×2+2+45×4−1120×3=320 by R1, R2, R3.3. Consider that nst(v)=1. Then m6+(v)≥2 by Claim 3.2. Note that m6+(v)≥4 if n3(1)(v)=2; m6+(v)≥5 if n3(1)(v)=3 by Lemma 2.6. Therefore, −τ(v→3-neighbors)+6∑i=1τ(fi→v)≥−78+min{−1120−13+4+45×2,−1120×2+5+45,−13×2+2+45×4}=439120 by R1, R3.2, R3.3. Hence, ω′(v)≥−65×3+439120=7120 by R1, R3.4. If nst(v)≥2, then m6+(v)≥4 and v has one Class five 2-neighbor and two 2-neighbors of Class four or Class five. Note that v is fake-adjacent a Δ-vertex by Class five 2-vertex, which indicates that v receives at least 45−612=310 by R7. Moreover, ω′(v)≥−1+min{−1110,−1}×2+4+45×2−78×3+310=340 by R1, R2, R3.4.
Subcase 5.5. Suppose n2(v)=4. If v is a heavy vertex, then n3(v)+n4(v)≤1. Note that n11+(v)=1 if n3(v)=1; n10+(v)=1 if n4(v)=1. So ω′(v)≥−65×4+45×6+min{−78+(95−611),−27+(95−610),0}=0 by R1, R2, R3.4, R4, R6. Consider that v is a light vertex. If m3(v)=1, then n3(1)(v)=0 by Claim 3.3. So ω′(v)≥5−4−13×2=13 by R1, R2, R3.2. If m4(v)=1, then nst(v)=0 by Claim 3.2 and Claim 3.3. Then ω′(v)≥5+12−4−1120×2=25 by R1, R2, R3.3. Next, consider that m5+(v)=6. If mA(v)≥2, then ω′(v)≥−65×4+45×6+6955×2−78×2=167220 by R1, R2, R3.4, and Claim 3.3. Consider that mA(v)=1. Note that m6+(v)≥3 if nst(v)≥1. Thus, ω′(v)≥−65×4+6955+min{45×3+3−78×2,45×6−1120×2}=23220 by R1, R2, R3.3, R3.4, and Claim 3.3. Finally, suppose mA(v)=0. If n3(1)(v)=0, then m6+(v)≥2 and v has either at least one Class five 2-neighbor or four Class four 2-neighbors. Hence, ω′(v)≥min{−65×3−1+2+45×4−13×2+(45−612),−1110×4+2+45×4−13×2}=215 by R1, R2, R3.2, R7. If n3(1)(v)=1, then m6+(v)≥4 and v has at least two Class five 2-neighbors by Lemma 2.6. Thus, ω′(v)≥−65×2−2+4+45×2−78+(45−612)×2−13=71120 by R1, R2, R3.2, R3.4, R7. If n3(1)(v)=2, then m6+(v)≥5 and v has four Class five 2-neighbors by Lemma 2.6. So ω′(v)≥−4+5+45−78×2+(45−612)×4=54 by R1, R2, R3.4, R7.
Subcase 5.6. Suppose n2(v)=5. If v is a heavy vertex, then n12+(v)=1. This shows that ω′(v)≥−65×5+45×6+(95−612)=110 by R1, R2, R6. Consider that v is a light vertex, which implies that m5+(v)=6 by Claim 3.3. If mA(v)≥2, then ω′(v)≥−65×5+45×6+6955×2−78=191440 by R1, R2, R3.4, and Claim 3.3. Consider that mA(v)=1. This implies that m6+(v)≥3 and v has at least one Class five 2-neighbor. It follows from R1, R2, R3.4, R7, and Claim 3.3 that ω′(v)≥−1−4×65+3+3×45−78+(45−612)+6955=123440. Finally, suppose mA(v)=0, which means that m6+(v)≥4 and v has at least three Class five 2-neighbors. So ω′(v)≥−3−65×2+4+45×2−78+(45−612)×3=940 by R1, R2, R3.4, R7.
Subcase 5.7. Suppose n2(v)=6. Obviously, v is a light vertex. Then m5+(v)=6 by Claim 3.3. If mA(v)≥2, then ω′(v)≥−65×6+45×6+6955×2=655 by R1, R2 and Claim 3.3. If mA(v)≤1, then m6+(v)≥5 and v has at least four Class five 2-neighbors. Hence, ω′(v)≥−4−65×2+5+45+(45−612)×4=35 by R1, R2, R7.
Case 6. d(v)=7 and then ω(v)=1.
Claim 3.4. If light v is incident with a configuration A-face f and f is incident with 2-neighbors and 3(1)-neighbors of v, then τ(f→v)≥95−610=65.
Subcase 6.1. Suppose n2(v)=0. Clearly, ω′(v)≥1+min{6,45×7}−1213×7=965 by R1, R3.4. Suppose n2(v)=k≥1. If v is a heavy vertex, then n2(v)+n3(v)≤6. If 1≤k≤2, then ω′(v)≥1+min{−107−(k−1)+87+5,−54k+12+6,−65k+45×7,−k+6}−1213(6−k)−27=−1865k+353455≥101455 by R1, R2, R3.4, R4. Consider that 3≤k≤6. If m4−(v)=1, then ω′(v)≥1+min{−107−(k−1)+87+5,−54×2−(k−2)+12+6,−k+6}−1213(6−k)−27=−113k+8191≥37 by R1, R2, R3.4, R4. Next, suppose m5+(v)=7. If 3≤k≤4, then ω′(v)≥1−65k+(6−k)+45(k+1)−1213(6−k)−27=−3165k+899455≥31455 by R1, R2, R3.4, R4, and Claim 3.2. Assume that k=5, we have n10+(v)=1 if n3(v)=1. Then ω′(v)≥1−65×5+45×7+min{−1213+(95−610),−27}=1135 by R1, R2, R3.4, R4, R6. If k=6, then n11+(v)=1. So ω′(v)≥1−65×6+45×7+(95−611)=3655 by R1, R2, R3.4, R6.
Subcase 6.2. Consider that v is a light vertex. If m3(v)=1, then n3(1)(v)≤6−k. Then ω′(v)≥1+min{−107−(k−1)+87+5,−k+6}−1213(6−k)−13=−113k+230273≥83273 by R1, R2, R3.2, R3.4. If m4(v)=1, then ω′(v)≥1+min{−54−(k−1)+12+6,−54×2−(k−2)+12+6,−k+6}−1213(7−k)=−113k+713≥0 by R1, R2, R3.4. Consider that m5+(v)=7. If 1≤k≤3, then ω′(v)≥1−65k+min{45×7−35(7−k),(7−k)+45k−1213(7−k)}=−3165k+2013≥765 by R1, R2, R3.4 and Claim 3.2. Suppose 4≤k≤5. If mA(v)≥1, then ω′(v)≥−3165k+2013+65≥2365 by Claim 3.4. Suppose mA(v)=0. Consider that k=4. Note that m6+(v)≥2 if nst(v)=1; m6+(v)≥5 if nst(v)≥2. Therefore, −τ(v→3-neighbors)+7∑i=1τ(fi→v)≥min{−1213−35×2+2+45×5,−1213×3+5+45×2,−35×3+45×7}=195 by R1, R3.3, R3.4. So ω′(v)≥1−65×4+195=0 by R2. If k=5, then m6+(v)≥3 and v has either at least two Class five 2-neighbors or one Class five 2-neighbor and four Class four 2-neighbors. Therefore, ω′(v)≥1+3+45×4−1213×2+min{−65×3−2+(45−611)×2,−1110×4−1+(45−611)}=149715 by R1, R2, R3.4, R7. Finally, suppose 6≤k≤7. If mA(v)≥2, then ω′(v)≥−3165k+2013+65×2≥35 by Claim 3.4. Next, consider that mA(v)=1. If k=6, then m6+(v)≥4 and v has at least two Class five 2-neighbors. Clearly, ω′(v)≥1−2−65×4+4+45×3−1213+(45−611)×2+65=991715 by R1, R2, R3, R7, and Claim 3.4. If k=7, then m6+(v)≥6 and v has at least five Class five 2-neighbors. Obviously, ω′(v)≥1−5−65×2+6+45+(45−611)×5+65=15855 by R1, R2, R3.4, R7, and Claim 3.4. Finally, consider that mA(v)=0. If k=6, then m6+(v)≥5 and v has at least four Class five 2-neighbors. Hence, ω′(v)≥1−4−65×2+45×2+5−1213+(45−611)×4=926715 by R1, R2, R3.4, R7. If k=7, then m6+(v)=7. Then ω′(v)≥1−7+7=1 by R1, R2.
Case 7. d(v)=8 and then ω(v)=2.
Claim 3.5. If light v is incident with a configuration A-face f and f is incident with 2-neighbors of v, then τ(f→v)≥95−610=65.
If m4−(v)=1, then ω′(v)≥2+min{−107−7+87+6,−54×2−6+12+7,−8+7}=57 by R1, R2. Consider that m5+(v)=8. Suppose n2(v)=k≤8. If k≤4, then ω′(v)≥2−65k+min{45×8−910(8−k),(8−k)+45k−(8−k)}=−310k+65≥0 by R1, R2, R3.4, R5.1. Next, consider that k≥5.
Consider that v is a heavy vertex. If k=5, then either n3(v)+n4(v)+n5(v)≤2 or n4(v)≤1 and n4(v)+n5(v)=3. Moreover, ω′(v)≥2−65×5+45×8+min{−1×2,−910−35×2}=310 by R1, R2, R3.4, R5.1. If k=6, then n3(v)+n4(v)+n5(v)≤1. So ω′(v)≥2−65×6+45×8+min{−1,−910}=15 by R1, R2, R3.4, R5.1. If k=7, then n10+(v)=1. Thus, ω′(v)≥2−65×7+45×8+(95−610)=65 by R1, R2, R6. Consider that v is a light vertex. If mA(v)≥1, then ω′(v)≥2+45×8−65×8+65=0 by R1, R2 and Claim 3.5. Next, consider that mA(v)=0. If k=5, then m6+(v)≥2 and v has either at least one Class five 2-vertex or four Class four 2-vertex. It follows from R1, R2, R3.4 that ω′(v)≥2+min{−65×4−1,−65−1110×4}+2+45×6−1×3=0. If k≥6, then m6+(v)≥4 and v has at least two Class five 2-neighbors. So ω′(v)≥2−65×6−2+45×4+4+(45−610)×2=25 by R1, R2, R7.
Case 8. d(v)=9 and then ω(v)=3.
If m4−(v)=1, then ω′(v)≥3+min{−107+87+7−87×8,−54×2+12+8−87×7,−87×9+8}=47 by R1, R2, R3.4. Consider that m5+(v)=9. Suppose n2(v)=k≤8. If k≤6, then ω′(v)≥3−65k+min{45×9−(9−k),(9−k)+45k−87(9−k)}=−15k+65≥0 by R1, R2, R3.4, R5.1, and Claim 3.2. Next, consider 7≤k≤9.
Suppose that v is a heavy vertex. If k=7, then either n3(v)+n4(v)+n5(v)+n6(v)≤1 or n5(v)+n6(v)=2. Clearly, ω′(v)≥3−65×7+45×9+min{−87,−35×2}=35 by R1, R2, R3.4, R5.2. If k=8, then n9+(v)=1. Thereby, ω′(v)≥3−65×8+45×9=35 by R1, R2. Consider that v is a light vertex. If v is not a big vertex, then ω′(v)≥0. Next, suppose that v is a big vertex. For configuration B-face (See Figure 1(b)), ω′(v′i)≥3−65×8+45×9=35(i=1,2) by R1∼R7. So configuration B-face has just one big vertex. If mB(v)≥1, then ω′(v)≥3+45×9−65×9+35=0 by R1, R2, R8.2. Suppose mB(v)=0. If k=7, then m6+(v)≥5. Obviously, ω′(v)≥3+45×4+5−65×7−87×2=1835 by R1, R2, R3.4. If k=8, then m6+(v)≥7. So ω′(v)≥3+45×2+7−65×8−87=67. If k=9, then m6+(v)=9, which indicates that ω′(v)≥3+9−9=3.
Case 9. d(v)=k≥10 and then ω(v)=k−6. Note that 2−7k>95−6k≥65.
If m4−(v)=1, then ω′(v)≥k−6+min{−107+k−2+87−(2−7k)(k−1),−54+k−1+12−(2−7k)(k−1),k−1−(2−7k)k}=0 by R1, R2, R3.4. Next, consider that m5+(v)=k. Suppose nst(v)=t≥0. Moreover, ω′(v)≥k−6+45(k−t)+t−(2−7k)t−(95−6k)(k−t)=1kt≥0 by R1, R3.4, R6, and Claim 3.2. From the above argument, it is clear that ω′(v′i)≥95−6d(v′i)(i=1,2) for configuration A-face (See Figure 1(a)) by R1∼R7.
Next, it follows from the above argument that ω′(f)≥0 if f is a configuration A-face or configuration B-face, which derives that ω′(f)≥0 for each f∈F(G).
Therefore, Theorem 1.6 is proved.
It is difficult to consider χi(G) and χli(G) for planar graph G that has g(G)≥4. So we consider the case of G where it does not have a 4−-cycle intersecting with a 5−-cycle. In addition, we will try to explore whether there exists a constant C such that χli(G)≤Δ+C for G has disjoint 4−-cycles.
Yuehua Bu: Conceptualization; Hongrui Zheng: Writing-original & draft; Hongrui Zheng and Hongguo Zhu: Writing-review & editing. All authors have read and agreed to the published version of the manuscript.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
This work was supported by the National Natural Science Foundation of China (12031018, 12201569).
The authors declare that they have no conflicts of interest.
[1] |
O. V. Borodin, A. O. Ivanova, List injective coloring of planar graphs, Discrete Math., 311 (2011), 154–165. https://doi.org/10.1016/j.disc.2010.10.008 doi: 10.1016/j.disc.2010.10.008
![]() |
[2] |
Y. Bu, C. Huang, List injective coloring of a class of planar graphs without short cycles, Discrete Math. Algorithms Appl., 10 (2018), 663–672. https://doi.org/10.1142/S1793830918500684 doi: 10.1142/S1793830918500684
![]() |
[3] |
Y. Bu, K. Lu, List injective coloring of planar graphs with girth 5, 6, 8, Discrete Appl. Math., 161 (2013), 1367–1377. https://doi.org/10.1016/j.dam.2012.12.017 doi: 10.1016/j.dam.2012.12.017
![]() |
[4] |
J. Cai, W. Li, W. Cai, M. Dehmer, List injective coloring of planar graphs, Appl. Math. Comput., 439 (2023), 127631. https://doi.org/10.1016/j.amc.2022.127631 doi: 10.1016/j.amc.2022.127631
![]() |
[5] |
H. Chen, List injective coloring of planar graphs with girth at least five, Bull. Korean Math. Soc., 61 (2024), 263–271. https://doi.org/10.4134/BKMS.b230097 doi: 10.4134/BKMS.b230097
![]() |
[6] |
H. Chen, J. Wu, List injective coloring of planar graphs with girth g≥6, Discrete Math., 339 (2016), 3043–3051. https://doi.org/10.1016/j.disc.2016.06.017 doi: 10.1016/j.disc.2016.06.017
![]() |
[7] |
M. Chen, G. Hahn, A. Raspaud, W. Wang, Some results on the injective chromatic number of graphs, J. Comb. Optim., 24 (2012), 299–318. https://doi.org/10.1007/s10878-011-9386-2 doi: 10.1007/s10878-011-9386-2
![]() |
[8] |
Q. Fang, L. Zhang, Sharp upper bound of injective coloring of planar graphs with girth at least 5, J. Comb. Optim., 44 (2022), 1161–1198. https://doi.org/10.1007/s10878-022-00880-z doi: 10.1007/s10878-022-00880-z
![]() |
[9] |
G. Hahn, J. Kratochvíl, J. Širáň, D. Sotteau, On the injective chromatic number of graphs, Discrete Math., 256 (2002), 179–192. https://doi.org/10.1016/S0012-365X(01)00466-6 doi: 10.1016/S0012-365X(01)00466-6
![]() |
[10] |
S. J. Kim, X. Lian, The square of every subcubic planar graph of girth at least 6 is 7-choosable, Discrete Math., 347 (2024), 113963. https://doi.org/10.1016/j.disc.2024.113963 doi: 10.1016/j.disc.2024.113963
![]() |
[11] |
W. Li, J. Cai, G. Yan, List injective coloring of planar graphs, Acta Math. Appl. Sin. Engl. Ser., 38 (2022), 614–626. https://doi.org/10.1007/s10255-022-1103-7 doi: 10.1007/s10255-022-1103-7
![]() |
[12] | B. Lužar, Planar graphs with largest injective chromatic number, IMFM Preprint series, 48 (2010), 1–6. |
[13] |
B. Lužar, R. Škrekovski, Counterexamples to a conjecture on injective colorings, Ars Math. Contemp., 8 (2015), 291–295. https://doi.org/10.26493/1855-3974.516.ada doi: 10.26493/1855-3974.516.ada
![]() |
[14] |
B. Lužar, R. Škrekovski, M. Tancer, Injective coloring of planar graphs with few colors, Discrete Math., 309 (2009), 5636–5649. https://doi.org/10.1016/j.disc.2008.04.005 doi: 10.1016/j.disc.2008.04.005
![]() |
[15] | G. Wegner, Graphs with given diameter and a coloring problem, Germany: University of Dortmund, 1977. |
[16] |
J. Yu, M. Chen, W. Wang, 2-Distance choosability of planar graphs with a restriction for maximum degree, Appl. Math. Comput., 448 (2023), 127949. https://doi.org/10.1016/j.amc.2023.127949 doi: 10.1016/j.amc.2023.127949
![]() |