×

On monochromatic paths and monochromatic cycles in edge coloured tournaments. (English) Zbl 0857.05054

The author gives various conditions sufficient to ensure that a tournament whose arcs are \(m\)-coloured has a node \(v\) such that for every other node \(x\) there is a monochromatic path from \(x\) to \(v\). One such condition is that each directed cycle of length at most four is quasi-monochromatic, i.e., with at most one exception its arcs all have the same colour.

MSC:

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

References:

[1] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[2] Berge, C.; Duchet, P., Recent problems and results about kernels in directed graphs, Discrete Math., 86, 27-31 (1990) · Zbl 0721.05027
[3] Galeana-Sánchez, H.; Neumann-Lara, V., On kernel-perfect critical digraphs, Discrete Math., 59, 257-265 (1986) · Zbl 0593.05034
[4] H. Galeana-Sánchez and S. Rajsbaum, Cycle pancyclism in tournaments III, submitted.; H. Galeana-Sánchez and S. Rajsbaum, Cycle pancyclism in tournaments III, submitted. · Zbl 0868.05028
[5] Sands, B.; Sauer, N.; Woodrow, R., On monochromatic paths in edge-coloured digraphs, J. Combin. Theory Ser. B, 33, 271-275 (1982) · Zbl 0488.05036
[6] Minggang, Shen, On monochromatic paths in \(m\)-coloured tournaments, J. Combin. Theory Ser. B, 45, 108-111 (1988) · Zbl 0654.05033
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.