An injective vertex coloring of a graph G is a coloring where no two vertices that share a common neighbor are assigned the same color. If for any list L of permissible colors with size k assigned to the vertices V(G) of a graph G, there exists an injective coloring <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\varphi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>φ</mi> </math></EquationSource> </InlineEquation> in which <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varphi (v)\in L(v)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>φ</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>L</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for each vertex <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$v\in V(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, then G is said to be injectively k-choosable. The notation <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\chi _{i}^{\ell }(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mrow> <mi>i</mi> </mrow> <mi>ℓ</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> represents the minimum value of k such that a graph G is injectively k-choosable. In this article, we demonstrate that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\chi _{i}^{\ell }(G)\le \Delta +3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mrow> <mi>i</mi> </mrow> <mi>ℓ</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> if <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\Delta \ge 13$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>13</mn> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\chi _{i}^{\ell }(G)\le \Delta +4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mrow> <mi>i</mi> </mrow> <mi>ℓ</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> if <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\Delta \ge 9$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>9</mn> </mrow> </math></EquationSource> </InlineEquation>, where G is a triangle-free planar graph with no intersecting 4-cycles nor intersecting 5-cycles.

List injective coloring of triangle-free planar graphs with no intersecting 4-cycles nor intersecting 5-cycles

期刊论文
发表日期：

2026年5月28日

查看全文

Hongyu Chen

摘要

An injective vertex coloring of a graph G is a coloring where no two vertices that share a common neighbor are assigned the same color. If for any list L of permissible colors with size k assigned to the vertices V(G) of a graph G, there exists an injective coloring $\varphi $ $φ$ in which $\varphi (v)\in L(v)$ $φ (v) \in L (v)$ for each vertex $v\in V(G)$ $v \in V (G)$ , then G is said to be injectively k-choosable. The notation $\chi _{i}^{\ell }(G)$ $χ_{i}^{ℓ} (G)$ represents the minimum value of k such that a graph G is injectively k-choosable. In this article, we demonstrate that $\chi _{i}^{\ell }(G)\le \Delta +3$ $χ_{i}^{ℓ} (G) \leq Δ + 3$ if $\Delta \ge 13$ $Δ \geq 13$ , and $\chi _{i}^{\ell }(G)\le \Delta +4$ $χ_{i}^{ℓ} (G) \leq Δ + 4$ if $\Delta \ge 9$ $Δ \geq 9$ , where G is a triangle-free planar graph with no intersecting 4-cycles nor intersecting 5-cycles.