For a sequence <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$S=(s_1,s_2,\ldots ,s_k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>s</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>s</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>s</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of positive integers with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$s_1\le s_2\le \cdots \le s_k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>s</mi> <mn>1</mn> </msub> <mo>≤</mo> <msub> <mi>s</mi> <mn>2</mn> </msub> <mo>≤</mo> <mo>⋯</mo> <mo>≤</mo> <msub> <mi>s</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, a packing S-coloring of a graph G is a partition of V(G) into k subsets <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$V_1, V_2,\ldots , V_k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>V</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>V</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>V</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> such that for each <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$1\le i \le k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation> the distance between any two distinct <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$x,y\in V_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>∈</mo> <msub> <mi>V</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is at least <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$s_i+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>s</mi> <mi>i</mi> </msub> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Tarhini and Togni (S-packing coloring of cubic Halin graphs, Discrete Appl. Math. 349 (2024) 53-58) posed an open problem: is every cubic Halin graph packing (1, 2, 2, 2, 2)-colorable? We show that this is true, improving a main result of Tarhini and Togni: every cubic Halin graph is packing (1, 2, 2, 2, 2, 2)-colorable.

On packing S-colorings of cubic Halin graphs

期刊论文
发表日期：

2026年5月16日

查看全文

Wei Yang,
Baoyindureng Wu

摘要

For a sequence $S=(s_1,s_2,\ldots ,s_k)$ $S = (s_{1}, s_{2}, \dots, s_{k})$ of positive integers with $s_1\le s_2\le \cdots \le s_k$ $s_{1} \leq s_{2} \leq \dots \leq s_{k}$ , a packing S-coloring of a graph G is a partition of V(G) into k subsets $V_1, V_2,\ldots , V_k$ $V_{1}, V_{2}, \dots, V_{k}$ such that for each $1\le i \le k$ $1 \leq i \leq k$ the distance between any two distinct $x,y\in V_i$ $x, y \in V_{i}$ is at least $s_i+1$ $s_{i} + 1$ . Tarhini and Togni (S-packing coloring of cubic Halin graphs, Discrete Appl. Math. 349 (2024) 53-58) posed an open problem: is every cubic Halin graph packing (1, 2, 2, 2, 2)-colorable? We show that this is true, improving a main result of Tarhini and Togni: every cubic Halin graph is packing (1, 2, 2, 2, 2, 2)-colorable.