A path with three blocks P(k, l, r) is an oriented path formed by k forward arcs followed by l backward arcs then r forward arcs. Gallai (Theory of graphs, Proc. Colloq., Tihany, 1966, Academic Press, 1968), Roy (Rev Française Informat Recherche Opérationelle 1:129–132, 1967), Hasse (Math Nachr 28:275–290, 1964/1965), Vitaver (Dokl Akad Nauk SSSR 147:758–789, 1962) proved that a k-chromatic digraph contains a directed path of length <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_789_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$k-1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. For large k, Burr (Subtrees of directed graphs and hypergraphs, 1980) conjectured that every k-chromatic digraph contains any oriented path of length <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_789_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$k-1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Addario-Berry et al. (J Comb Theory Ser B 97:620–626, 2007) confirmed Burr’s conjecture for paths with two blocks. We prove that any <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_789_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">$(2k+1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-chromatic digraph, <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_789_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$k\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, contains a path P(1, k, 1). Besides, for every <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_789_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$(k+4)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mn>4</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-chromatic digraph D, there exists an integer <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_789_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$l\ge k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>l</mi> <mo>≥</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation> such that D contains a P(1, l, 1).

On Paths with Three Blocks of the Form P(1, k, 1) in Digraphs

期刊论文
发表日期：

2025年10月31日

查看全文

Maidoun Mortada,
Amin El Sahili,
Zahraa Mohsen

摘要

A path with three blocks P(k, l, r) is an oriented path formed by k forward arcs followed by l backward arcs then r forward arcs. Gallai (Theory of graphs, Proc. Colloq., Tihany, 1966, Academic Press, 1968), Roy (Rev Française Informat Recherche Opérationelle 1:129–132, 1967), Hasse (Math Nachr 28:275–290, 1964/1965), Vitaver (Dokl Akad Nauk SSSR 147:758–789, 1962) proved that a k-chromatic digraph contains a directed path of length $k-1$ $k - 1$ . For large k, Burr (Subtrees of directed graphs and hypergraphs, 1980) conjectured that every k-chromatic digraph contains any oriented path of length $k-1$ $k - 1$ . Addario-Berry et al. (J Comb Theory Ser B 97:620–626, 2007) confirmed Burr’s conjecture for paths with two blocks. We prove that any $(2k+1)$ $(2 k + 1)$ -chromatic digraph, $k\ge 2$ $k \geq 2$ , contains a path P(1, k, 1). Besides, for every $(k+4)$ $(k + 4)$ -chromatic digraph D, there exists an integer $l\ge k$ $l \geq k$ such that D contains a P(1, l, 1).