×

About paths with three blocks. (English) Zbl 1468.05132

Summary: We show that every oriented path of order \(n\geqslant 4\) with three blocks, in which two consecutive of them are of length 1, is contained in every \((n+1)\)-chromatic digraph.

MSC:

05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: Link

References:

[1] L. W. Beineke, Derived graphs and digraphs, In:Beitrage zur Graphentheorie (Eds. H. Sachs, H. J. Voss and H. Walter), Teubner, Leipzig, (1968), 17-23. · Zbl 0179.29204
[2] S. A. Burr, Subtrees of directed graphs and hypergraphs, In:Proc. 11th Southeastern Conf. Combinatorics, Graph Theory and Computing, Florida Atlantic Univ., Boca Raton, Fla. I Vol. 28 (1980), 227-239. · Zbl 0453.05022
[3] L. Addario-Berry, F. Havet and S. Thomassé, Paths with two blocks innchromatic digraphs,J. Combin. Theory Ser. B97 (2007), 620-626. · Zbl 1119.05049
[4] A. El Sahili and M. Kouider, About paths with two blocks,J. Graph Theory55 (2007), 221-226. · Zbl 1121.05065
[5] A. El Sahili, Functions and line digraphs,J. Graph Theory4 (2003), 296-303. · Zbl 1031.05058
[6] T. Gallai, On directed paths and circuits, In:Theory of Graphs, (Eds. P. Erdős and G. Katona), Academic Press, New York (1968), 115-118. · Zbl 0159.54403
[7] M. Hasse, Zur algeraischen Begündung der Graphentheorie I,Math. Nachr.28 (1964/1965), 275-290.
[8] F. Havet and S. Thomassé, Oriented hamiltonian paths in tournaments: a proof of Rosenfeld’s conjecture,J. Combin. Theory Ser B78 (2000), 243-273. · Zbl 1026.05053
[9] B. Roy, Nombre chromatique et plus longs chemins d’un graphe,Rev. Française Automat. Informat. Recherche Opérationelle Sér. Rouge, 1 (1967), 127-132. · Zbl 0157.31302
[10] L. M. Vitaver, Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix,Dokl. Akad. Nauk SSSR147 (1962), 758-789 (in Russian) · Zbl 0126.39302
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.