<p>Given a positive integer <i>d</i>, the class <i>d</i>-DIR is defined as all those intersection graphs formed from a finite collection of line segments in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\({\mathbb R}^2\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation> having at most <i>d</i> slopes. Since each slope induces an interval graph, it easily follows for every <i>G</i> in <i>d</i>-DIR with clique number at most <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq4.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation> that the chromatic number <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of <i>G</i> is at most <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(d\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mi>ω</mi> </mrow> </math></EquationSource> </InlineEquation>. We show for every even value of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq4.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation> how to construct a graph in <i>d</i>-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq1.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>-binding function of <i>d</i>-DIR is <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq9.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="61" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega \mapsto d\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo>↦</mo> <mi>d</mi> <mi>ω</mi> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq4.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation> even and <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="129" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega \mapsto d(\omega -1)+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ω</mi> <mo>↦</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>ω</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq4.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation> odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_737_Article_IEq13.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(d=2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

The \(\chi \)-Binding Function of d-Directional Segment Graphs

  • Lech Duraj,
  • Ross J. Kang,
  • Hoang La,
  • Jonathan Narboni,
  • Filip Pokrývka,
  • Clément Rambaud,
  • Amadeus Reinald

摘要

Given a positive integer d, the class d-DIR is defined as all those intersection graphs formed from a finite collection of line segments in \({\mathbb R}^2\) R 2 having at most d slopes. Since each slope induces an interval graph, it easily follows for every G in d-DIR with clique number at most \(\omega \) ω that the chromatic number \(\chi (G)\) χ ( G ) of G is at most \(d\omega \) d ω . We show for every even value of \(\omega \) ω how to construct a graph in d-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the \(\chi \) χ -binding function of d-DIR is \(\omega \mapsto d\omega \) ω d ω for \(\omega \) ω even and \(\omega \mapsto d(\omega -1)+1\) ω d ( ω - 1 ) + 1 for \(\omega \) ω odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case \(d=2\) d = 2 .