<p>A graph <i>G</i> is (1, 3)-colorable if its vertices can be partitioned into subsets <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2973_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">$V_1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2973_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">$V_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> so that every vertex in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2973_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$G[V_1]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo stretchy="false">[</mo> <msub> <mi>V</mi> <mn>1</mn> </msub> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> has degree at most 1 and every vertex in <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2973_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$G[V_2]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo stretchy="false">[</mo> <msub> <mi>V</mi> <mn>2</mn> </msub> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> has degree at most 3. We prove that every graph with maximum average degree at most 28/9 is (1, 3)-colorable.</p>

Sparse Critical Graphs for Defective (1, 3)-Coloring

期刊论文
出版模式：

开放获取
发表日期：

2025年9月26日

查看全文

Alexandr Kostochka,
Jingwei Xu,
Xuding Zhu

摘要

A graph G is (1, 3)-colorable if its vertices can be partitioned into subsets $V_1$ $V_{1}$ and $V_2$ $V_{2}$ so that every vertex in $G[V_1]$ $G [V_{1}]$ has degree at most 1 and every vertex in $G[V_2]$ $G [V_{2}]$ has degree at most 3. We prove that every graph with maximum average degree at most 28/9 is (1, 3)-colorable.