The square of a graph G, denoted by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$G^2$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>G</mi> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation>, has the same vertex set as G and has an edge between two vertices if the distance between them in G is at most 2. Thomassen (2018) and independently, Hartke, Jahanbekam and Thomas (2016) proved that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\chi (G^2) \le 7$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <msup> <mi>G</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation> if G is a subcubic planar graph. A natural question is whether <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\chi _{\ell }(G^2) \le 7$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>ℓ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msup> <mi>G</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation> or not if G is a subcubic planar graph. Recently, Kim and Lian (2024) proved that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\chi _{\ell }(G^2) \le 7$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>ℓ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msup> <mi>G</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation> if G is a subcubic planar graph of girth at least 6. In this paper, we prove that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\chi _{\ell }(G^2) \le 7$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>ℓ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msup> <mi>G</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation> if G is a subcubic planar graph without 4-cycles and 5-cycles, which improves the result of Kim and Lian.

The Square of Every Subcubic Planar Graph Without 4-cycles and 5-cycles is 7-choosable

期刊论文
发表日期：

2026年3月4日

查看全文

Ligang Jin,
Yingli Kang,
Seog-Jin Kim

摘要

The square of a graph G, denoted by $G^2$ $G^{2}$ , has the same vertex set as G and has an edge between two vertices if the distance between them in G is at most 2. Thomassen (2018) and independently, Hartke, Jahanbekam and Thomas (2016) proved that $\chi (G^2) \le 7$ $χ (G^{2}) \leq 7$ if G is a subcubic planar graph. A natural question is whether $\chi _{\ell }(G^2) \le 7$ $χ_{ℓ} (G^{2}) \leq 7$ or not if G is a subcubic planar graph. Recently, Kim and Lian (2024) proved that $\chi _{\ell }(G^2) \le 7$ $χ_{ℓ} (G^{2}) \leq 7$ if G is a subcubic planar graph of girth at least 6. In this paper, we prove that $\chi _{\ell }(G^2) \le 7$ $χ_{ℓ} (G^{2}) \leq 7$ if G is a subcubic planar graph without 4-cycles and 5-cycles, which improves the result of Kim and Lian.