> Detailanzeige

Wang, Xiao; Zhang, Donghan

The χ -Boundedness of P 2 ∪ P 3 -Free Graphs

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: E-Artikel
  • Titel: The χ -Boundedness of P 2 ∪ P 3 -Free Graphs
  • Beteiligte: Wang, Xiao; Zhang, Donghan
  • Erschienen: Hindawi Limited, 2022
  • Erschienen in: Journal of Mathematics
  • Sprache: Englisch
  • DOI: 10.1155/2022/2071887
  • ISSN: 2314-4785; 2314-4629
  • Schlagwörter: General Mathematics
  • Entstehung:
  • Anmerkungen:
  • Beschreibung: <jats:p>In the early 1980s, Gyárfás introduced the concept of the <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M3"> <mi>χ</mi> </math> </jats:inline-formula>-bound with <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M4"> <mi>χ</mi> </math> </jats:inline-formula>-binding functions thereby extending the notion of perfectness. There are a number of challenging conjectures about the <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M5"> <mi>χ</mi> </math> </jats:inline-formula>-bound. Let <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M6"> <mi>χ</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> </math> </jats:inline-formula>, <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M7"> <mi>ω</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> </math> </jats:inline-formula>, and <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M8"> <mi mathvariant="normal">Δ</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> </math> </jats:inline-formula> be the chromatic number, clique number, and maximum degree of a graph <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M9"> <mi>G</mi> </math> </jats:inline-formula>, respectively. In this paper, we prove that if <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M10"> <mi>G</mi> </math> </jats:inline-formula> is a triangle-free and <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M11"> <mfenced open="(" close=")" separators="|"> <mrow> <msub> <mrow> <mi>P</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msub> <mo>∪</mo> <msub> <mrow> <mi>P</mi> </mrow> <mrow> <mn>3</mn> </mrow> </msub> </mrow> </mfenced> </math> </jats:inline-formula>-free graph, then <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M12"> <mi>χ</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> <mo>≤</mo> <mn>3</mn> </math> </jats:inline-formula> unless <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M13"> <mi>G</mi> </math> </jats:inline-formula> is one of eight graphs with <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M14"> <mi mathvariant="normal">Δ</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> <mo>=</mo> <mn>5</mn> </math> </jats:inline-formula> and <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M15"> <mi>χ</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> <mo>=</mo> <mn>4</mn> </math> </jats:inline-formula>, where the eight graphs are extended from the Grötzsch graph as a Mycielskian of a 5-cycle graph. Moreover, we also show that <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M16"> <mi>χ</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> <mo>≤</mo> <mn>3</mn> <mi>ω</mi> <mfenced open="(" close=")" separators="|"> <mrow> <mi>G</mi> </mrow> </mfenced> </math> </jats:inline-formula> if <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M17"> <mi>G</mi> </math> </jats:inline-formula> is a <jats:inline-formula> <math xmlns="http://www.w3.org/1998/Math/MathML" id="M18"> <mfenced open="{" close="}" separators="|"> <mrow> <msub> <mrow> <mi>P</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msub> <mo>∪</mo> <msub> <mrow> <mi>P</mi> </mrow> <mrow> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mrow> <mi>W</mi> </mrow> <mrow> <mn>4</mn> </mrow> </msub> </mrow> </mfenced> </math> </jats:inline-formula>-free graph.</jats:p>
  • Zugangsstatus: Freier Zugang