{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:24Z","timestamp":1787321124190,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Consider a directed analogue of the random graph process on $n$ vertices, where the $n(n-1)$ edges are ordered uniformly at random and revealed one at a time. It is known that with high probability (w.h.p.) the first digraph in this process with both in-degree and out-degree $\\geq q$ has a $q$-edge-coloring with a Hamilton cycle in each color. We show that this coloring can be constructed online, where each edge must be irrevocably colored as soon as it appears. In a similar fashion, for the undirected random graph process, we present an online $n$-edge-coloring algorithm which yields w.h.p. $q$ disjoint rainbow Hamilton cycles in the first graph containing $q$ disjoint Hamilton cycles.<\/jats:p>","DOI":"10.1137\/17m1112273","type":"journal-article","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T11:39:57Z","timestamp":1530185997000},"page":"1505-1539","source":"Crossref","is-referenced-by-count":0,"title":["Packing Directed Hamilton Cycles Online"],"prefix":"10.1137","volume":"32","author":[{"given":"Michael","family":"Anastos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Briggs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,28]]},"reference":[{"key":"atypb1","first-page":"173","author":"Ajtai M.","year":"1985","journal-title":"Amsterdam"},{"key":"atypb2","unstructured":"S. Bernstein,\n                      The Theory of Probabilities\n                      , Gastehizdat, Moscow, 1946."},{"key":"atypb3","unstructured":"J. Briggs, A. M. Frieze, M. Krivelevich, P.S. Loh, and B. Sudakov,\n                      Packing Hamilton cycles online\n                      ,arXiv:1608.04976, 2016."},{"key":"atypb4","unstructured":"B. Bolloba\u0301s,\n                      The evolution of sparse graphs\n                      , in Graph Theory and Combinatorics proceedings, Cambridge Combinatorial Conference in Honour of Paul Erdo\u0308s, 1984, B. Bolloba\u0301s, ed., Academic, London, pp. 335-357."},{"key":"atypb5","first-page":"23","volume":"28","author":"Bolloba\u0301s B.","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301005004"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"P. Erdo\u0308s, and A. Re\u0301nyi,\n                      On the strength of connectedness of a random graph\n                      , Acta Math. Hungar., 12.1-2 (1961), pp. 261-267.","DOI":"10.1007\/BF02066689"},{"key":"atypb8","unstructured":"W. Feller,\n                      An Introduction to Probability Theory and Its Applications\n                      , Vol. I, 3rd ed., John Wiley & Sons, New York, 1968."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1945-08448-1"},{"key":"atypb10","first-page":"167","author":"Ferber A.","year":"2016","journal-title":"Berlin"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90037-5"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20475"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"A. Frieze and M. Karon\u0301ski,\n                      Introduction to Random Graphs\n                      , Cambridge University Press, Cambridge, 2015.","DOI":"10.1017\/CBO9781316339831"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucin\u0301ski,\n                      Random Graphs\n                      , John Wiley & sons, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20510"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90021-3"},{"key":"atypb18","first-page":"760","volume":"17","author":"Korshunov A.","year":"1976","journal-title":"Soviet Math. Dokl."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20302"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/110849171"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831200020X"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120903"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1112273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:32Z","timestamp":1787317592000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1112273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1112273"],"URL":"https:\/\/doi.org\/10.1137\/17m1112273","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}