Paths with two blocks in \(n\)-chromatic digraphs
type: Item
instance of: scholarly article
title: Paths with two blocks in \(n\)-chromatic digraphs
zbMATH Open document ID: 1119.05049
author: Stéphan Thomassé
author: Louigi Addario-Berry
author: Frédéric Havet
published in: Journal of Combinatorial Theory. Series B
publication date: 2007-06-08T00:00:00Z
review text: Let \(k+l=n-1 \geq 3\) and let \(D\) be an \(n\)-chromatic digraph. Proving a conjecture of El-Sahili, the authors show that \(D\) contains a \(P(k,l).\) (Here \(P(k,l)\) is an oriented path of order \(k+l+1\) starting with \(k\) forward arcs and followed by \(l\) backward arcs for some \(k \geq 1\) and \(l\geq 1.\)) Several connections to related results and open problems are mentioned.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5162681
zbMATH Keywords: universal digraph
zbMATH Keywords: unavoidable digraph
zbMATH Keywords: \(n\)-chromatic digraph
zbMATH Keywords: oriented path
reviewed by: Hans Peter Künzi
MaRDI profile type: Publication
full work available at URL: j.jctb.2006.10.001
OpenAlex ID: W2143815444
cites work: On the existence of specified cycles in a tournament
cites work: Diconnected Orientations and a Conjecture of Las Vergnas
cites work: Q3900086
cites work: Paths with two blocks in \(k\)-chromatic digraphs
cites work: Trees in tournaments
cites work: About paths with two blocks
cites work: Graph Theory and Probability
cites work: Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
cites work: Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture
cites work: Q5545303
cites work: Nombre chromatique et plus longs chemins d'un graphe
DOI: 10.1016/J.JCTB.2006.10.001
description: scientific article; zbMATH DE number 5162681