Paths With Three Blocks In Digraphs

MaRDI QIDQ6380760zbMATH OpenFDO

Authors Maidoun Mortada, Amine El Sahili

Publication date 19 October 2021

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Abstract: 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. We prove that any $(2k+1)$-chromatic digraph contains a path $P(1,k,1)$. However the existence of $P(1,l,1)$ with $lgeqk$ is established in any $(k+4)$-chromatic digraph. In general, we establish a quadratic bound for paths with three blocks.

This page was built for publication: Paths With Three Blocks In Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380760)