Connected Colourings of Complete Graphs and Hypergraphs

Preprint English OPEN
Leader, Imre; Tan, Ta Sheng;
(2014)
  • Subject: Mathematics - Combinatorics
    arxiv: Astrophysics::Galaxy Astrophysics | Mathematics::Combinatorics | Astrophysics::Cosmology and Extragalactic Astrophysics

Gallai's colouring theorem states that if the edges of a complete graph are 3-coloured, with each colour class forming a connected (spanning) subgraph, then there is a triangle that has all 3 colours. What happens for more colours: if we $k$-colour the edges of the comp... View more
  • References (14)
    14 references, page 1 of 2

    [1] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83(3) (2001), 532-562.

    [2] R. N. Ball, A. Pultr, and P. Vojtˇechovsky´, Coloured graphs without colorful cycles, Combinatorica 27(4) (2007), 407-427.

    [3] K. Diao, G. Liu, D. Rautenbach, and P. Zhao, A note on the least number of edges of 3- uniform hypergraphs with upper chromatic number 2, Discrete Math. 306 (2006), 670-672.

    [4] P. Duchet, Hypergraphs, Handbook of Combinatorics (1995), 381-432.

    [5] S. Fujita, C. Magnant, and K. Ozeki, Rainbow Generalizations of Ramsey Theory: A Survey, Graphs Combin. 26 (2010), 1-30.

    [6] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25-66 (in German).

    [7] V. Gurvich, Decomposing complete edge-chromatic graphs and hypergraphs. Revisited, Discrete Applied Math. 157(14) (2009), 3069-3085.

    [8] A. Gy´arf´as, G. N. Sark¨ozy, A. Sebo˝ and S. Selkow, Ramsey-type results for Gallai colorings, J. Graph Theory 64(3) (2010), 233-243.

    [9] A. Gy´arf´as and G. N. Sark¨ozy, Gallai colorings of non-complete graphs, Discrete Math. 310 (2010), 977-980.

    [10] A. Gy´arf´as and G. Simony, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46(3) (2004), 211-216.

  • Similar Research Results (1)
  • Metrics
Share - Bookmark