<p>A graph <i>G</i> is said to be <i>2-divisible</i> if for each induced subgraph <i>H</i> of <i>G</i>, either <i>V</i>(<i>H</i>) is a stable set or <i>V</i>(<i>H</i>) can be partitioned into two sets <i>A</i> and <i>B</i> such that <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="123" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega (H[A])&lt; \omega (H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">[</mo> <mi>A</mi> <mo stretchy="false">]</mo> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="124" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega (H[B])&lt; \omega (H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">[</mo> <mi>B</mi> <mo stretchy="false">]</mo> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. A graph <i>G</i> is called <i>perfectly divisible</i> if for each induced subgraph <i>H</i> of <i>G</i>, the set <i>V</i>(<i>H</i>) can be partitioned into two sets <i>A</i> and <i>B</i> such that <i>H</i>[<i>A</i>] is perfect and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="124" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega (H[B])&lt; \omega (H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">[</mo> <mi>B</mi> <mo stretchy="false">]</mo> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. A graph <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_{2}\cup P_{3}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> is the disjoint union of paths <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_{2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq8.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_{3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>3</mn> </msub> </math></EquationSource> </InlineEquation>. A bull is a graph consisting of a triangle with two disjoint pendant edges. In this paper, we prove that <OrderedList> <ListItem> <ItemNumber>(a)</ItemNumber> <ItemContent> <p>each <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">\((C_{5}, P_{2}\cup P_{3})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>5</mn> </msub> <mo>,</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free graph is 2-divisible;</p> </ItemContent> </ListItem> <ListItem> <ItemNumber>(b)</ItemNumber> <ItemContent> <p>a <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="103" /> </InlineMediaObject> <EquationSource Format="TEX">\((bull, P_{2}\cup P_{3})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>b</mi> <mi>u</mi> <mi>l</mi> <mi>l</mi> <mo>,</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mn>3</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free graph <i>G</i> with <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega (G)\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> has a partition (<i>X</i>,&#xa0;<i>Y</i>) such that <i>G</i>[<i>X</i>] is perfect and <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2926_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="120" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega (G[Y])&lt; \omega (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">[</mo> <mi>Y</mi> <mo stretchy="false">]</mo> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> if <i>G</i> admits no homogeneous set.</p> </ItemContent> </ListItem> </OrderedList></p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the structure of some classes of \((P_{2}\cup P_{3})\)-free graphs

  • Zijian Deng,
  • Caibing Chang

摘要

A graph G is said to be 2-divisible if for each induced subgraph H of G, either V(H) is a stable set or V(H) can be partitioned into two sets A and B such that \(\omega (H[A])< \omega (H)\) ω ( H [ A ] ) < ω ( H ) and \(\omega (H[B])< \omega (H)\) ω ( H [ B ] ) < ω ( H ) . A graph G is called perfectly divisible if for each induced subgraph H of G, the set V(H) can be partitioned into two sets A and B such that H[A] is perfect and \(\omega (H[B])< \omega (H)\) ω ( H [ B ] ) < ω ( H ) . A graph \(P_{2}\cup P_{3}\) P 2 P 3 is the disjoint union of paths \(P_{2}\) P 2 and \(P_{3}\) P 3 . A bull is a graph consisting of a triangle with two disjoint pendant edges. In this paper, we prove that (a)

each \((C_{5}, P_{2}\cup P_{3})\) ( C 5 , P 2 P 3 ) -free graph is 2-divisible;

(b)

a \((bull, P_{2}\cup P_{3})\) ( b u l l , P 2 P 3 ) -free graph G with \(\omega (G)\ge 3\) ω ( G ) 3 has a partition (XY) such that G[X] is perfect and \(\omega (G[Y])< \omega (G)\) ω ( G [ Y ] ) < ω ( G ) if G admits no homogeneous set.