About paths with two blocks
Amine El Sahili, Mekkia Kouider · Journal of Graph Theory · 2007
Abstract The function f ( n ) is defined to be the smallest integer such that any f ( n )‐chromatic digraph contains all paths with two blocks P ( k , j ) with k + j = n − 1. El Sahili conjectured that f ( n ) = n . We prove in this paper that f ( n ) ≤ n + 1. Our argument yields a very short and direct proof of the Gallai–Roy result about directed paths. We also treat the problem under some supplementary conditions. One of them is used to give a simple proof of a result of Saks and Sós about claws. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 221–226, 2007