Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We call the tournament T an m-coloured tournament if the arcs of T are coloured with m-colours. If v is a vertex of an m-coloured tournament T, we denote by ξ(v) the set of colours assigned to the arcs with v as an endpoint.

In this paper is proved that if T is an m-coloured tournament with |ξ(v)|≤2 for each vertex v of T, and T satisfies at least one of the two following properties (1) m≠3 or (2) m=3 and T contains no C3 (the directed cycle of length 3 whose arcs are coloured with three distinct colours). Then there is a vertex v of T such that for every other vertex x of T, there is a monochromatic directed path from x to v.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam, 1973

  2. Berge, C., Duchet, P.: Recent problems and results about kernels in directed graphs. Discrete Math. 86, 27–31 (1990)

    Google Scholar 

  3. Chvátal, V., Lovász, L.: Every directed graphs has a semi-kernel. in Hypergraph Seminar, Lecture Notes in Math. 411, Springer, Berlin, pp. 175, 1974

  4. Galeana-Sánchez, H.: On monochromatic paths and monochromatics cycles in edge coloured tournaments. Discrete Mathematics 156, 103–112 (1996)

    Google Scholar 

  5. Galeana-Sánchez, H.: Kernels in edge-coloured digraphs. Discrete Mathematics 184, 87–99 (1998)

    Google Scholar 

  6. Galeana-Sánchez, H., García-Ruvalcaba, J.J.: Kernels in the closure of coloured digraphs. Discussiones Mathematicae, Graph Theory 20, 243–254 (2000)

    Google Scholar 

  7. Sands, B., Sauer, N., Woodrow, R.: On monochromatic paths in edge coloured digraphs. J. Combin. Theory, Ser. B 33, 271–275 (1982)

    Google Scholar 

  8. Minggang, S.: On monochromatic paths in m-coloured tournaments. J. Combin. Theory Ser. B 45, 108–111 (1988)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Instituto de Matemáticas, UNAM, Ciudad Universitaria, Circuito Exterior, 04510, México, D.F., México

    Hortensia Galeana-Sánchez

  2. Facultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario No. 100, Centro, 50000, Toluca, Edo. de México, México

    Rocío Rojas-Monroy

Authors
  1. Hortensia Galeana-Sánchez
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Rocío Rojas-Monroy
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Hortensia Galeana-Sánchez.

Additional information

Received: April, 2003

Rights and permissions

Reprints and permissions

About this article

Cite this article

Galeana-Sánchez, H., Rojas-Monroy, R. Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments. Graphs and Combinatorics 21, 307–317 (2005). https://doi.org/10.1007/s00373-005-0618-z

Download citation

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-005-0618-z

Keywords

Mathematics Subject Classification (2000)