Almost partitioning every 2-edge-coloured complete k-graph into k monochromatic tight cycles
Lo, Allan1; Pfenninger, Vincent2
1 University of Birmingham Birmingham B15 2TT United Kingdom
2 Graz University of Technology Institute of Discrete Mathematics Steyrergasse 30 8010 Graz Austria
Innovations in Graph Theory, Volume 1 (2024), pp. 1-19.

A k-uniform tight cycle is a k-graph with a cyclic order of its vertices such that every k consecutive vertices from an edge. We show that for k≥3, every red-blue edge-coloured complete k-graph on n vertices contains k vertex-disjoint monochromatic tight cycles that together cover n-o(n) vertices.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.1
Lo, Allan 1; Pfenninger, Vincent 2

1 University of Birmingham Birmingham B15 2TT United Kingdom
2 Graz University of Technology Institute of Discrete Mathematics Steyrergasse 30 8010 Graz Austria
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2024__1__1_0,
     author = {Lo, Allan and Pfenninger, Vincent},
     title = {Almost partitioning every $2$-edge-coloured complete $k$-graph into~$k$ monochromatic tight cycles},
     journal = {Innovations in Graph Theory},
     pages = {1--19},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {1},
     year = {2024},
     doi = {10.5802/igt.1},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.1/}
}
TY  - JOUR
AU  - Lo, Allan
AU  - Pfenninger, Vincent
TI  - Almost partitioning every $2$-edge-coloured complete $k$-graph into $k$ monochromatic tight cycles
JO  - Innovations in Graph Theory
PY  - 2024
SP  - 1
EP  - 19
VL  - 1
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.1/
DO  - 10.5802/igt.1
LA  - en
ID  - IGT_2024__1__1_0
ER  - 
%0 Journal Article
%A Lo, Allan
%A Pfenninger, Vincent
%T Almost partitioning every $2$-edge-coloured complete $k$-graph into $k$ monochromatic tight cycles
%J Innovations in Graph Theory
%D 2024
%P 1-19
%V 1
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.1/
%R 10.5802/igt.1
%G en
%F IGT_2024__1__1_0
Lo, Allan; Pfenninger, Vincent. Almost partitioning every $2$-edge-coloured complete $k$-graph into $k$ monochromatic tight cycles. Innovations in Graph Theory, Volume 1 (2024), pp. 1-19. doi : 10.5802/igt.1. https://igt.centre-mersenne.org/articles/10.5802/igt.1/

[1] Allen, Peter; Böttcher, Julia; Cooley, Oliver; Mycroft, Richard Tight cycles and regular slices in dense hypergraphs, J. Combin. Theory Ser. A, Volume 149 (2017), pp. 30-100 | DOI | MR | Zbl

[2] Alon, Noga; Frankl, Peter; Lovász, László The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc., Volume 298 (1986) no. 1, pp. 359-370 | DOI | MR | Zbl

[3] Allen, Peter Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles, Combin. Probab. Comput., Volume 17 (2008) no. 4, pp. 471-486 | DOI | MR | Zbl

[4] Balogh, József; Barát, János; Gerbner, Dániel; Gyárfás, András; Sárközy, Gábor N. Partitioning 2-edge-colored graphs by monochromatic paths and cycles, Combinatorica, Volume 34 (2014) no. 5, pp. 507-526 | DOI | MR | Zbl

[5] Bustamante, Sebastián; Corsten, Jan; Frankl, Nóra; Pokrovskiy, Alexey; Skokan, Jozef Partitioning edge-colored hypergraphs into few monochromatic tight cycles, SIAM J. Discrete Math., Volume 34 (2020) no. 2, pp. 1460-1471 | DOI | MR | Zbl

[6] Bustamante, Sebastián; Hàn, Hiệp; Stein, Maya Almost partitioning 2-colored complete 3-uniform hypergraphs into two monochromatic tight or loose cycles, J. Graph Theory, Volume 91 (2019) no. 1, pp. 5-15 | DOI | MR | Zbl

[7] Bustamante, Sebastián; Stein, Maya Partitioning 2-coloured complete k-uniform hypergraphs into monochromatic ℓ-cycles, European J. Combin., Volume 71 (2018), pp. 213-221 | DOI | MR | Zbl

[8] Bessy, Stéphane; Thomassé, Stéphan Partitioning a graph into a cycle and an anticycle, a proof of Lehel’s conjecture, J. Combin. Theory Ser. B, Volume 100 (2010) no. 2, pp. 176-180 | DOI | MR | Zbl

[9] DeBiasio, Louis; Nelsen, Luke L. Monochromatic cycle partitions of graphs with large minimum degree, J. Combin. Theory Ser. B, Volume 122 (2017), pp. 634-667 | DOI | MR | Zbl

[10] Erdős, Paul; Gyárfás, András; Pyber, László Vertex coverings by monochromatic cycles and trees, J. Combin. Theory Ser. B, Volume 51 (1991) no. 1, pp. 90-95 | DOI | MR | Zbl

[11] Gale, David The game of Hex and the Brouwer fixed-point theorem, Amer. Math. Monthly, Volume 86 (1979) no. 10, pp. 818-827 | DOI | MR | Zbl

[12] Gerencsér, László; Gyárfás, András On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., Volume 10 (1967), pp. 167-170 | MR | Zbl

[13] Gyárfás, András; Lehel, Jeno A Ramsey-type problem in directed and bipartite graphs, Period. Math. Hungar., Volume 3 (1973) no. 3-4, pp. 299-304 | DOI | MR

[14] Garbe, Frederik; Mycroft, Richard; Lang, Richard; Lo, Allan; Sanhueza-Matamala, Nicolás Partitioning 2-coloured complete 3-uniform hypergraphs into two monochromatic tight cycles (in preparation)

[15] Gyárfás, András; Ruszinkó, Miklós; Sárközy, Gábor N.; Szemerédi, Endre An improved bound for the monochromatic cycle partition number, J. Combin. Theory Ser. B, Volume 96 (2006) no. 6, pp. 855-873 | DOI | MR | Zbl

[16] Gyárfás, András; Sárközy, Gábor N. Monochromatic path and cycle partitions in hypergraphs, Electron. J. Combin., Volume 20 (2013) no. 1, Paper no. P18, 8 pages | DOI | MR | Zbl

[17] Gyárfás, András Vertex covers by monochromatic pieces—a survey of results and problems, Discrete Math., Volume 339 (2016) no. 7, pp. 1970-1977 | DOI | MR | Zbl

[18] Gyárfás, András Vertex coverings by monochromatic paths and cycles, J. Graph Theory, Volume 7 (1983) no. 1, pp. 131-135 | DOI | MR | Zbl

[19] Korándi, Dániel; Lang, Richard; Letzter, Shoham; Pokrovskiy, Alexey Minimum degree conditions for monochromatic cycle partitioning, J. Combin. Theory Ser. B, Volume 146 (2021), pp. 96-123 | DOI | MR | Zbl

[20] Letzter, Shoham Monochromatic cycle partitions of 2-coloured graphs with minimum degree 3n/4, Electron. J. Combin., Volume 26 (2019) no. 1, Paper no. P1.19, 67 pages | DOI | MR | Zbl

[21] Lo, Allan; Pfenninger, Vincent Towards Lehel’s conjecture for 4-uniform tight cycles, Electron. J. Combin., Volume 30 (2023) no. 1, Paper no. P1.13, 36 pages | DOI | MR | Zbl

[22] Pokrovskiy, Alexey Partitioning edge-coloured complete graphs into monochromatic cycles and paths, J. Combin. Theory Ser. B, Volume 106 (2014), pp. 70-97 | DOI | MR | Zbl

[23] Pokrovskiy, Alexey Partitioning a graph into a cycle and a sparse graph, Discrete Math., Volume 346 (2023) no. 1, Paper no. 113161, 21 pages | DOI | MR | Zbl

[24] Simonovits, Miklós; Szemerédi, Endre Embedding graphs into larger graphs: results, methods, and problems, Building bridges II—mathematics of László Lovász (Bolyai Soc. Math. Stud.), Volume 28, Springer, Berlin, 2019, pp. 445-592 | DOI | MR | Zbl

[25] Stein, Maya Monochromatic paths in 2-edge-coloured graphs and hypergraphs, Electron. J. Combin., Volume 30 (2023), Paper no. P1.53, 12 pages | DOI | Zbl

[26] Sárközy, Gábor N. Improved monochromatic loose cycle partitions in hypergraphs, Discrete Math., Volume 334 (2014), pp. 52-62 | DOI | MR | Zbl

[27] Łuczak, Tomasz; Rödl, Vojtěch; Szemerédi, Endre Partitioning two-coloured complete graphs into two monochromatic cycles, Combin. Probab. Comput., Volume 7 (1998) no. 4, pp. 423-436 | DOI | MR | Zbl

[28] Łuczak, Tomasz R(C n ,C n ,C n )≤(4+o(1))n, J. Combin. Theory Ser. B, Volume 75 (1999) no. 2, pp. 174-187 | DOI | MR | Zbl

Cited by Sources: