Loading [MathJax]/jax/output/SVG/jax.js
Research article Special Issues

On the list injective coloring of planar graphs without a 4-cycle intersecting with a 5-cycle

  • 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

    Related Papers:

    [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):vV(G)}. A list injective coloring of G is an injective coloring of G such that c(v)L(v) for each vertex vG. 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)=1ikd(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 HG. 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 uvE(G). By G having the fewest edges, Guv 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 3d(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 uvE(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, Gvv1 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, Gvv1 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=[v1v1vv2v2] be a 5-face with d(v)=6, d(v1)=d(v2)=2, and d(v2)=3. Then v is a heavy vertex.

    Proof. Assume to the contrary that v is a light vertex. Clearly, Gvv1 has an injective L-coloring. Decolor v, v1, and v2. Clearly, |F(v1)|d(v)1+Δ2=Δ+3. It follows from v and v2 being light vertices that we can recolor v1, v, and v2 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 Gvv1 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 vV(G)d(v)=fF(G)d(f)=2|E(G)|, we derive the following equation:

    vV(G)(d(v)6)+fF(G)(2d(f)6)=12.

    Then we construct the weight function ω(v)=d(v)6 for each vV(G) and ω(f)=2d(f)6 for each fF(G), which means that xV(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:

    0xV(G)F(G)ω(x)=xV(G)F(G)ω(x)=12.

    It shows that G does not exist, so Theorem 1.6 is proved. Then τ(uv) shows the weight that u transfers to v, and τ(ufv) denotes the weight that u transfers to v by f, where u,vV(G) and fF(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=[v1v1vv2v2] with 6d(v)8, 2d(vi)3, and d(vi)10(i=1,2) (See Figure 1(a)). configurationB-face: Suppose f=[v1v1vv2v2] with d(v)=9, d(vi)=2 and d(vi)9(i=1,2) (See Figure 1(b)).

    Figure 1.  Discharging rule R8.

    The discharging rules

    R1 Let f be a 4+-face. Then τ(fincidentvertices)=26d(f).

    R2 Let uvE(G) and d(u)3. If v is a Class one(resp., Class two, Class three, Class four, Class five) 2-vertex, then τ(uv)=107(resp.,54,65,1110,1).

    R3 Let d(v)=3 and uvE(G).

    R3.1 Suppose that v is a light 3(0)-vertex and u is a heavy vertex with 3d(u)7. Then τ(uv)=13.

    R3.2 Suppose that v is a heavy 3(0)-vertex. If d(u)=4(resp., 5d(u)7), then τ(uv)=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 τ(uv)=710(resp.,34,45,910,1110). Assume m4+(v)=3, if d(u)=5(resp., 6, 7, 8, 9), then τ(uv)=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 τ(uv)=78(resp.,1213,1,87). If d(u)10, then τ(uv)=27d(u).

    R4 Let d(v)=4 and uvE(G). If d(u)=5(resp., 6d(u)7), then τ(uv)=130(resp., 27).

    R5 Suppose 8d(u)9 such that uvE(G).

    R5.1 If d(v)=3,4 except for 3(1)-vertex, then τ(uv)=910 when d(u)=8 and τ(uv)=1 when d(u)=9.

    R5.2 If d(v)=5, then τ(uv)=35.

    R5.3 If d(v)=6, then τ(uv)=35 when d(u)=9.

    R6 Suppose 3d(v)8 except for strong 3(1)-vertex. If d(u)10 such that uvE(G), then τ(uv)=956d(u)65.

    R7 Let d(u)10 and 6d(v)8. If u is fake-adjacent to v by a Class five 2-vertex, then τ(uv)=456d(u).

    R8 Suppose f=[v1v1vv2v2]. After R1R6, the 9-vertex v is called big 9-vertex if ω(v)<0.

    R8.1 If f is a configuration A-face, then τ(vif)=9103d(vi)(i=1,2) through v1v2 and τ(fv)956min{d(v1),d(v2)} (See Figure 1(a)).

    R8.2 If v is a big vertex and f is a configuration B-face, then τ(vif)=310 through v1v2 and f transfers 35 to each big 9-vertex equally (See Figure 1(b)).

    Firstly, we check ω(v) for each vV(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 2i=1τ(fiv)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 2i=1τ(fiv)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 3i=1τ(fiv)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, 3i=1τ(viv)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 3i=1τ(viv)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 τ(vv1)13 by R3.1. If d(v2)=4, then d(v3)12; if 5d(v2)7, then d(v3)9; otherwise, d(v2),d(v3)8. So 3i=2τ(viv)min{130+(95612),13+1,910×2}=43 by R3.2, R5.1, R6. Furthermore, ω(v)3+213+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, 3i=2τ(viv)min{710+(95612),34+(95611),45+(95610),910+1110}=2 by R3.3, R5, R6. Thereby, ω(v)3+21+2=0 by R1, R2. If m4+(v)=3, then τ(vv1)+3i=1τ(fiv)min{54+12+2,65+45×3}=65 by R1, R2. So ω(v)3+65+min{12+(95612),1120+(95611),35+(95610),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, τ(vv1)+3i=1τ(fiv)107+87+1=57 by R1, R2. Thus, ω(v)3+57+min{78+(2712),1213+(2711),1+(2710),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 4i=1τ(fiv)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, τ(v3-neighbors)+τ(11+-neighborv)min{13×3+(95611),13×2}=23 by R3.1, R6. Hence, ω(v)2+323=13. Otherwise, suppose that v is a light vertex, which implies that vi(1i4) are not light 3-vertices by Lemma 2.1. Clearly, ω(v)2+3130×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 τ(vv1)+4i=1τ(fiv)107+87+2=127; if v1 is a Class two 2-vertex, then τ(vv1)+4i=1τ(fiv)54+12+3=94; if m5+(v)=4, then τ(vv1)+4i=1τ(fiv)65+45×4=2; otherwise m6+(v1)=2 and m4(v)=1, then τ(vv1)+4i=1τ(fiv)1+3=2. Therefore, τ(vv1)+4i=1τ(fiv)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 τ(v3-neighbors)+τ(6+-neighborsv)min{27,13+910,13×2+(95612)}=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, τ(vv1)τ(vv2)+4i=1τ(fiv)min{1071+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 6d(v3)7, then d(v4)9; otherwise, d(v3),d(v4)8. This indicates that 4i=3τ(viv)min{95612,130+(95611),27+1,910×2}=97 by R4, R5.1, R6. So ω(v)2+57+97=0.

    Claim 3.1. Let 5d(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, 5i=1τ(fiv)min{4,4+12,45×5}=4. Therefore, ω(v)1+471012×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, τ(v2-neighbor)+5i=1τ(fiv)min{107+87+3,54+12+4,65+45×5,1+4}=197. Note that n10+(v)=1 if n3(v)=3. Therefore, τ(v3-neighbors)τ(v4-neighbors)+τ(10+-neighborsv)min{13×3+(95610),13×2130×2}=1115 by R3.1, R3.2, R4, R6. Hence, ω(v)1+1971115=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, τ(v2-neighbors)+5i=1τ(fiv)min{1071+87+3,54×2+12+4,65×2+45×5,2+4}=85. Note that n11+(v)=1 if n3(v)=2. Moreover, τ(v3-neighbors)τ(v4-neighbors)+τ(11+-neighborv)min{13×2+(95611),13130×2}=25 by R3.1, R4, R6. Thus, ω(v)1+8525=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, τ(v2-neighbors)+5i=1τ(fiv)min{1072+87+3,54×21+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+(95612),130+(95611)}=0 by R3.1, R4, R5.2, R6.

    Claim 3.2. Suppose d(v)6, m5+(v)=d(v), and nst(v)=t. If 1td(v)1, then m6+(v)t+1, w.l.o.g., m6+(v)t for t0.

    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 τ(fv)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 τ(fv)95611=6955.

    Subcase 5.1. Suppose n2(v)=0. If v is a heavy vertex, then n3(v)5. According to R1, 6i=1τ(fiv)min{45×6,5}=245. Therefore, ω(v)2455×7827=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)54×78341120=15 by R1, R3.3, R3.4 and Claim 3.1. Consider that m5+(v)=6. If nst(v)4, then ω(v)45×64×781120×2=15 by R1, R3.3, R3.4. If nst(v)5, then m6+(v)=6 by Claim 3.2. It follows that ω(v)66×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 τ(v3-neighbors)+τ(v4-neighbors)max{78×4,27×5}=72 by R3.4, R4. According to R1, R2, τ(v2-neighbor)+6i=1τ(fiv)min{107+87+4,54+12+5,65+45×6,1+5}=185. Therefore, ω(v)18572=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 τ(v2-neighbor)=1 by R2 and Claim 3.3. So ω(v)1+578×3341120=340 by R1, R3.3, R3.4, and Claim 3.1. Consider that m5+(v)=6. Suppose nst(v)=t5. Then τ(v2-neighbor)+6i=1τ(fiv)65+t+45(6t)=15t+185 by R1, R2 and Claim 3.2. Thereby, ω(v)15t+18578t1120(5t)=18t+1720940 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, τ(v2-neighbors)+6i=1τ(fiv)min{1071+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×227}=51140 by R3.4, R4, R5.3. Otherwise, consider that v is a light vertex. By Claim 3.3 and R2, τ(v2-neighbors)=2. If m3(v)=1, then n3(1)(v)2 by Claim 3.3. Then ω(v)5278×213×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+1278×21120×2=1320 by R1, R2, R3.3, R3.4, and Claim 3.1. Finally, consider that m5+(v)=6. Suppose nst(v)=t4. If t=0, then ω(v)65×2+45×61120×4=15 by R1, R2, R3.3; if 1t3, then ω(v)65×2+t+1+45(5t)78t1120(4t)=18t+25140 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+4578×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+(95610),7827}=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)53782×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+123781120×2=2140 by R1, R2, R3.3, R3.4, and Claim 3.3. Consider that m5+(v)=6. Suppose nst(v)=t3. If mA(v)1, then ω(v)65×3+t+45(6t)+695578t1120(3t)=18t+177220189440 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×613×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)651110×2+2+45×41120×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, τ(v3-neighbors)+6i=1τ(fiv)78+min{112013+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 45612=310 by R7. Moreover, ω(v)1+min{1110,1}×2+4+45×278×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+(95611),27+(95610),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)5413×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+1241120×2=25 by R1, R2, R3.3. Next, consider that m5+(v)=6. If mA(v)2, then ω(v)65×4+45×6+6955×278×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+378×2,45×61120×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×31+2+45×413×2+(45612),1110×4+2+45×413×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×22+4+45×278+(45612)×213=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+4578×2+(45612)×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+(95612)=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×278=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)14×65+3+3×4578+(45612)+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)365×2+4+45×278+(45612)×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)465×2+5+45+(45612)×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 τ(fv)95610=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)=k1. If v is a heavy vertex, then n2(v)+n3(v)6. If 1k2, then ω(v)1+min{107(k1)+87+5,54k+12+6,65k+45×7,k+6}1213(6k)27=1865k+353455101455 by R1, R2, R3.4, R4. Consider that 3k6. If m4(v)=1, then ω(v)1+min{107(k1)+87+5,54×2(k2)+12+6,k+6}1213(6k)27=113k+819137 by R1, R2, R3.4, R4. Next, suppose m5+(v)=7. If 3k4, then ω(v)165k+(6k)+45(k+1)1213(6k)27=3165k+89945531455 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)165×5+45×7+min{1213+(95610),27}=1135 by R1, R2, R3.4, R4, R6. If k=6, then n11+(v)=1. So ω(v)165×6+45×7+(95611)=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)6k. Then ω(v)1+min{107(k1)+87+5,k+6}1213(6k)13=113k+23027383273 by R1, R2, R3.2, R3.4. If m4(v)=1, then ω(v)1+min{54(k1)+12+6,54×2(k2)+12+6,k+6}1213(7k)=113k+7130 by R1, R2, R3.4. Consider that m5+(v)=7. If 1k3, then ω(v)165k+min{45×735(7k),(7k)+45k1213(7k)}=3165k+2013765 by R1, R2, R3.4 and Claim 3.2. Suppose 4k5. If mA(v)1, then ω(v)3165k+2013+652365 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, τ(v3-neighbors)+7i=1τ(fiv)min{121335×2+2+45×5,1213×3+5+45×2,35×3+45×7}=195 by R1, R3.3, R3.4. So ω(v)165×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×41213×2+min{65×32+(45611)×2,1110×41+(45611)}=149715 by R1, R2, R3.4, R7. Finally, suppose 6k7. If mA(v)2, then ω(v)3165k+2013+65×235 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)1265×4+4+45×31213+(45611)×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)1565×2+6+45+(45611)×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)1465×2+45×2+51213+(45611)×4=926715 by R1, R2, R3.4, R7. If k=7, then m6+(v)=7. Then ω(v)17+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 τ(fv)95610=65.

    If m4(v)=1, then ω(v)2+min{1077+87+6,54×26+12+7,8+7}=57 by R1, R2. Consider that m5+(v)=8. Suppose n2(v)=k8. If k4, then ω(v)265k+min{45×8910(8k),(8k)+45k(8k)}=310k+650 by R1, R2, R3.4, R5.1. Next, consider that k5.

    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)265×5+45×8+min{1×2,91035×2}=310 by R1, R2, R3.4, R5.1. If k=6, then n3(v)+n4(v)+n5(v)1. So ω(v)265×6+45×8+min{1,910}=15 by R1, R2, R3.4, R5.1. If k=7, then n10+(v)=1. Thus, ω(v)265×7+45×8+(95610)=65 by R1, R2, R6. Consider that v is a light vertex. If mA(v)1, then ω(v)2+45×865×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×41,651110×4}+2+45×61×3=0. If k6, then m6+(v)4 and v has at least two Class five 2-neighbors. So ω(v)265×62+45×4+4+(45610)×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+787×8,54×2+12+887×7,87×9+8}=47 by R1, R2, R3.4. Consider that m5+(v)=9. Suppose n2(v)=k8. If k6, then ω(v)365k+min{45×9(9k),(9k)+45k87(9k)}=15k+650 by R1, R2, R3.4, R5.1, and Claim 3.2. Next, consider 7k9.

    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)365×7+45×9+min{87,35×2}=35 by R1, R2, R3.4, R5.2. If k=8, then n9+(v)=1. Thereby, ω(v)365×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)), ω(vi)365×8+45×9=35(i=1,2) by R1R7. So configuration B-face has just one big vertex. If mB(v)1, then ω(v)3+45×965×9+35=0 by R1, R2, R8.2. Suppose mB(v)=0. If k=7, then m6+(v)5. Obviously, ω(v)3+45×4+565×787×2=1835 by R1, R2, R3.4. If k=8, then m6+(v)7. So ω(v)3+45×2+765×887=67. If k=9, then m6+(v)=9, which indicates that ω(v)3+99=3.

    Case 9. d(v)=k10 and then ω(v)=k6. Note that 27k>956k65.

    If m4(v)=1, then ω(v)k6+min{107+k2+87(27k)(k1),54+k1+12(27k)(k1),k1(27k)k}=0 by R1, R2, R3.4. Next, consider that m5+(v)=k. Suppose nst(v)=t0. Moreover, ω(v)k6+45(kt)+t(27k)t(956k)(kt)=1kt0 by R1, R3.4, R6, and Claim 3.2. From the above argument, it is clear that ω(vi)956d(vi)(i=1,2) for configuration A-face (See Figure 1(a)) by R1R7.

    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 fF(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 g6, 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
  • Reader Comments
  • © 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(365) PDF downloads(68) Cited by(0)

Figures and Tables

Figures(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog