For an integer 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> with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$0\le s_1\le s_2\le \cdots \le s_k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</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> </mrow> </math></EquationSource> </InlineEquation>, an S-packing edge-coloring of a graph G is a partition of E(G) into k subsets <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$E_1, E_2,\ldots , E_k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>E</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>E</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>E</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>, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$d_{L(G)}(e,e')\ge s_i+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mrow> <mi>L</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo>,</mo> <msup> <mi>e</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <msub> <mi>s</mi> <mi>i</mi> </msub> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$e, e' \in E_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>,</mo> <msup> <mi>e</mi> <mo>′</mo> </msup> <mo>∈</mo> <msub> <mi>E</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$d_{L(G)}(e,e')$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mrow> <mi>L</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo>,</mo> <msup> <mi>e</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denotes the distance of e and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$e'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>e</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> in the line graph L(G) of G. Liu, Santana, Short (J. Graph Theory 104 (2023) 851-885) proved that every subcubic multigraph is <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$(1, 2^7)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <msup> <mn>2</mn> <mn>7</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-packing edge-colorable. In this paper, we show that every subcubic claw-free graph distinct from <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$ C_3\Box K_2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>C</mi> <mn>3</mn> </msub> <mo>□</mo> <msub> <mi>K</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$(1,2^5)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <msup> <mn>2</mn> <mn>5</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-packing edge-colorable, and this bound is sharp.

On S-packing edge-colorings of subcubic claw-free graphs

期刊论文
发表日期：

2025年10月15日

查看全文

Wei Yang,
Baoyindureng Wu

摘要

For an integer sequence $S=(s_1,s_2,\ldots ,s_k)$ $S = (s_{1}, s_{2}, \dots, s_{k})$ with $0\le s_1\le s_2\le \cdots \le s_k$ $0 \leq s_{1} \leq s_{2} \leq \dots \leq s_{k}$ , an S-packing edge-coloring of a graph G is a partition of E(G) into k subsets $E_1, E_2,\ldots , E_k$ $E_{1}, E_{2}, \dots, E_{k}$ such that for each $1\le i \le k$ $1 \leq i \leq k$ , $d_{L(G)}(e,e')\ge s_i+1$ $d_{L (G)} (e, e^{'}) \geq s_{i} + 1$ for any $e, e' \in E_i$ $e, e^{'} \in E_{i}$ , where $d_{L(G)}(e,e')$ $d_{L (G)} (e, e^{'})$ denotes the distance of e and $e'$ $e^{'}$ in the line graph L(G) of G. Liu, Santana, Short (J. Graph Theory 104 (2023) 851-885) proved that every subcubic multigraph is $(1, 2^7)$ $(1, 2^{7})$ -packing edge-colorable. In this paper, we show that every subcubic claw-free graph distinct from $ C_3\Box K_2$ $C_{3} □ K_{2}$ is $(1,2^5)$ $(1, 2^{5})$ -packing edge-colorable, and this bound is sharp.