Buchumschlag

Minimum degree conditions for monochromatic cycle partitioning

A classical result of Erdős, Gyárfás and Pyber states that any r-edge-coloured complete graph has a partition into O(r2log⁡r) monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant c such that any r-edge-coloure...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Korándi, Dániel (VerfasserIn) , Lang, Richard (VerfasserIn) , Letzter, Shoham (VerfasserIn) , Pokrovskiy, Alexey (VerfasserIn)
Dokumenttyp: Article (Journal)
Sprache:Englisch
Veröffentlicht: 2021
In: Journal of combinatorial theory
Year: 2020, Jahrgang: 146, Pages: 96-123
DOI:10.1016/j.jctb.2020.07.005
Online-Zugang:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.jctb.2020.07.005
Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S0095895620300721
Volltext
Verfasserangaben:Dániel Korándi, Richard Lang, Shoham Letzter, Alexey Pokrovskiy

MARC

LEADER 00000caa a2200000 c 4500
001 1747731072
003 DE-627
005 20220819100727.0
007 cr uuu---uuuuu
008 210208r20212020xx |||||o 00| ||eng c
024 7 |a 10.1016/j.jctb.2020.07.005  |2 doi 
035 |a (DE-627)1747731072 
035 |a (DE-599)KXP1747731072 
035 |a (OCoLC)1341391898 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 27  |2 sdnb 
100 1 |a Korándi, Dániel  |d 1990-  |e VerfasserIn  |0 (DE-588)1102417378  |0 (DE-627)860345580  |0 (DE-576)470228326  |4 aut 
245 1 0 |a Minimum degree conditions for monochromatic cycle partitioning  |c Dániel Korándi, Richard Lang, Shoham Letzter, Alexey Pokrovskiy 
264 1 |c 2021 
300 |a 28 
336 |a Text  |b txt  |2 rdacontent 
337 |a Computermedien  |b c  |2 rdamedia 
338 |a Online-Ressource  |b cr  |2 rdacarrier 
500 |a Available online 27 August 2020 
500 |a Gesehen am 08.02.2021 
520 |a A classical result of Erdős, Gyárfás and Pyber states that any r-edge-coloured complete graph has a partition into O(r2log⁡r) monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant c such that any r-edge-coloured graph on n vertices with minimum degree at least n/2+c⋅rlog⁡n has a partition into O(r2) monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight. 
534 |c 2020 
650 4 |a Dirac-type problems 
650 4 |a Hamilton cycles 
650 4 |a Monochromatic cycle partitioning 
650 4 |a Ramsey theory 
700 1 |a Lang, Richard  |e VerfasserIn  |0 (DE-588)122670008X  |0 (DE-627)1747737372  |4 aut 
700 1 |a Letzter, Shoham  |e VerfasserIn  |4 aut 
700 1 |a Pokrovskiy, Alexey  |e VerfasserIn  |4 aut 
773 0 8 |i Enthalten in  |t Journal of combinatorial theory  |d Orlando, Fla. : Academic Press, 1971  |g 146(2021), Seite 96-123  |h Online-Ressource  |w (DE-627)266892426  |w (DE-600)1469158-9  |w (DE-576)104193816  |7 nnas  |a Minimum degree conditions for monochromatic cycle partitioning 
773 1 8 |g volume:146  |g year:2021  |g pages:96-123  |g extent:28  |a Minimum degree conditions for monochromatic cycle partitioning 
856 4 0 |u https://doi.org/10.1016/j.jctb.2020.07.005  |x Verlag  |x Resolving-System  |z lizenzpflichtig  |3 Volltext 
856 4 0 |u https://www.sciencedirect.com/science/article/pii/S0095895620300721  |x Verlag  |z lizenzpflichtig  |3 Volltext 
951 |a AR 
992 |a 20210208 
993 |a Article 
994 |a 2021 
998 |g 122670008X  |a Lang, Richard  |m 122670008X:Lang, Richard  |d 110000  |d 110300  |e 110000PL122670008X  |e 110300PL122670008X  |k 0/110000/  |k 1/110000/110300/  |p 2 
999 |a KXP-PPN1747731072  |e 3849771709 
BIB |a Y 
SER |a journal 
JSO |a {"name":{"displayForm":["Dániel Korándi, Richard Lang, Shoham Letzter, Alexey Pokrovskiy"]},"origin":[{"dateIssuedKey":"2021","dateIssuedDisp":"2021"}],"id":{"doi":["10.1016/j.jctb.2020.07.005"],"eki":["1747731072"]},"physDesc":[{"extent":"28 S."}],"relHost":[{"recId":"266892426","language":["eng"],"type":{"bibl":"periodical","media":"Online-Ressource"},"disp":"Minimum degree conditions for monochromatic cycle partitioningJournal of combinatorial theory","note":["Gesehen am 13.01.14"],"part":{"pages":"96-123","year":"2021","extent":"28","volume":"146","text":"146(2021), Seite 96-123"},"titleAlt":[{"title":"Journal of combinatorial theory / B"},{"title":"JCTB"}],"pubHistory":["10.1971 - 103.2013; Vol. 104.2014 -"],"title":[{"title_sort":"Journal of combinatorial theory","title":"Journal of combinatorial theory","subtitle":"JCTB"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"eki":["266892426"],"zdb":["1469158-9"]},"origin":[{"publisherPlace":"Orlando, Fla.","dateIssuedDisp":"1971-","publisher":"Academic Press","dateIssuedKey":"1971"}]}],"person":[{"role":"aut","roleDisplay":"VerfasserIn","display":"Korándi, Dániel","given":"Dániel","family":"Korándi"},{"given":"Richard","family":"Lang","role":"aut","display":"Lang, Richard","roleDisplay":"VerfasserIn"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Letzter, Shoham","given":"Shoham","family":"Letzter"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Pokrovskiy, Alexey","given":"Alexey","family":"Pokrovskiy"}],"title":[{"title":"Minimum degree conditions for monochromatic cycle partitioning","title_sort":"Minimum degree conditions for monochromatic cycle partitioning"}],"type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Available online 27 August 2020","Gesehen am 08.02.2021"],"language":["eng"],"recId":"1747731072"} 
SRT |a KORANDIDANMINIMUMDEG2021 

Ähnliche Einträge