<p>Let <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_t\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_t\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation> denote the path and the cycle on <i>t</i> vertices, respectively. A <i>diamond</i> (resp. <i>gem</i>) consists of a <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq5.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> (resp. <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>) and a new vertex adjacent to all vertices of the <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq5.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> (resp. <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>), a <i>kite</i> consists of a <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation> and a new vertex adjacent to three consecutive vertices of the <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>, and a <i>paraglider</i> consists of a <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation> and a new vertex adjacent to three vertices of the <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_4\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>. A class <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq13.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation> of graphs is said to be <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq14.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation>-polydet (Schiermeyer and Randerath in Graphs Combin 35:1–31, 2019) if <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq13.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation> has a polynomial binding function <i>f</i> and there exists a polynomial time algorithm to determine a coloring of <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq16.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\in \mathcal{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∈</mo> <mi mathvariant="script">G</mi> </mrow> </math></EquationSource> </InlineEquation> with at most <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq17.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="62" /> </InlineMediaObject> <EquationSource Format="TEX">\(f(\omega (G))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> colors. In 2021, Choudum et al. (Disc. Math. 344:112244, 2021) determined the structures of <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq18.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">\((P_7,C_7,C_4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, diamond)-free and <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq18.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">\((P_7,C_7,C_4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>4</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, gem)-frees, and gave correspondingly tight upper bounds to the chromatic numbers of these graphs. In this paper, we study the structure of <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq20.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\((P_7, C_5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>5</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, kite, paraglider)-free graphs, which is a superfamily of <InlineEquation ID="IEq21"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq20.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\((P_7, C_5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>5</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, diamond)-free graphs. We show that there is a unique connected imperfect <InlineEquation ID="IEq22"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq20.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\((P_7, C_5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>5</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, kite, paraglider)-free graph with <InlineEquation ID="IEq23"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq23.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="123" /> </InlineMediaObject> <EquationSource Format="TEX">\(\delta (G)\ge \omega (G)+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, which has no clique cutsets, no universal cliques, and no pair of vertices of which one’s neighborhoods contains the other’s. As a consequence, we show that <InlineEquation ID="IEq24"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq20.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\((P_7, C_5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>7</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>5</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, kite, paraglider)-free graphs are <InlineEquation ID="IEq25"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq14.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>χ</mi> </math></EquationSource> </InlineEquation>-polydet with a binding function <InlineEquation ID="IEq26"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2932_Article_IEq26.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega (G)+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Structure and Coloring of a Family of (\(P_7, C_5\))-Free Graphs

  • Ran Chen,
  • Baogang Xu

摘要

Let \(P_t\) P t and \(C_t\) C t denote the path and the cycle on t vertices, respectively. A diamond (resp. gem) consists of a \(P_3\) P 3 (resp. \(P_4\) P 4 ) and a new vertex adjacent to all vertices of the \(P_3\) P 3 (resp. \(P_4\) P 4 ), a kite consists of a \(P_4\) P 4 and a new vertex adjacent to three consecutive vertices of the \(P_4\) P 4 , and a paraglider consists of a \(C_4\) C 4 and a new vertex adjacent to three vertices of the \(C_4\) C 4 . A class \(\mathcal{G}\) G of graphs is said to be \(\chi \) χ -polydet (Schiermeyer and Randerath in Graphs Combin 35:1–31, 2019) if \(\mathcal{G}\) G has a polynomial binding function f and there exists a polynomial time algorithm to determine a coloring of \(G\in \mathcal{G}\) G G with at most \(f(\omega (G))\) f ( ω ( G ) ) colors. In 2021, Choudum et al. (Disc. Math. 344:112244, 2021) determined the structures of \((P_7,C_7,C_4\) ( P 7 , C 7 , C 4 , diamond)-free and \((P_7,C_7,C_4\) ( P 7 , C 7 , C 4 , gem)-frees, and gave correspondingly tight upper bounds to the chromatic numbers of these graphs. In this paper, we study the structure of \((P_7, C_5\) ( P 7 , C 5 , kite, paraglider)-free graphs, which is a superfamily of \((P_7, C_5\) ( P 7 , C 5 , diamond)-free graphs. We show that there is a unique connected imperfect \((P_7, C_5\) ( P 7 , C 5 , kite, paraglider)-free graph with \(\delta (G)\ge \omega (G)+1\) δ ( G ) ω ( G ) + 1 , which has no clique cutsets, no universal cliques, and no pair of vertices of which one’s neighborhoods contains the other’s. As a consequence, we show that \((P_7, C_5\) ( P 7 , C 5 , kite, paraglider)-free graphs are \(\chi \) χ -polydet with a binding function \(\omega (G)+1\) ω ( G ) + 1 .