{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:46Z","timestamp":1740122386884,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11901605","12101069"],"award-info":[{"award-number":["11901605","12101069"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10878-022-00859-w","type":"journal-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T15:06:59Z","timestamp":1650899219000},"page":"3153-3164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Triangle packing and covering in dense random graphs"],"prefix":"10.1007","volume":"44","author":[{"given":"Zhongzheng","family":"Tang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1729-5960","authenticated-orcid":false,"given":"Zhuo","family":"Diao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,25]]},"reference":[{"key":"859_CR1","volume-title":"The probabilistic method, Wiley-Interscience series in discrete mathematics and optimization","author":"N Alon","year":"2008","unstructured":"Alon N, Spencer JH (2008) The probabilistic method, Wiley-Interscience series in discrete mathematics and optimization, 3rd edn. Wiley, New York","edition":"3"},{"issue":"6","key":"859_CR2","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1016\/j.jctb.2006.03.001","volume":"96","author":"J Balogh","year":"2006","unstructured":"Balogh J, Keevash P, Sudakov B (2006) On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs. J Combin Theory Ser B 96(6):919\u2013932","journal-title":"J Combin Theory Ser B"},{"key":"859_CR3","unstructured":"Baron JD (2016) Two problems on cycles in random graphs. PhD thesis, Rutgers University-Graduate School-New Brunswick"},{"issue":"5","key":"859_CR4","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1017\/S0963548320000115","volume":"29","author":"P Bennett","year":"2020","unstructured":"Bennett P, Dudek A, Zerbib S (2020) Large triangle packings and Tuza\u2019s conjecture in sparse random graphs. Combin Probab Comput 29(5):757\u2013779","journal-title":"Combin Probab Comput"},{"key":"859_CR5","doi-asserted-by":"crossref","unstructured":"Botler F, Fernandes CG, Guti\u00e9rrez J (2018) On Tuza\u2019s conjecture for graphs with treewidth at most 6. In: Anais do III Encontro de Teoria da Computa\u00e7\u00e3o. SBC","DOI":"10.5753\/etc.2018.3141"},{"key":"859_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.entcs.2019.08.016","volume":"346","author":"F Botler","year":"2019","unstructured":"Botler F, Fernandes C, Guti\u00e9rrez J (2019) On Tuza\u2019s conjecture for triangulations and graphs with small treewidth. Electron Notes Theor Comput Sci 346:171\u2013183","journal-title":"Electron Notes Theor Comput Sci"},{"key":"859_CR7","doi-asserted-by":"crossref","unstructured":"Chalermsook P, Khuller S, Sukprasert P, Uniyal S (2020) Multi-transversals for triangles and the Tuza\u2019s conjecture. In: Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 1955\u20131974","DOI":"10.1137\/1.9781611975994.121"},{"issue":"1","key":"859_CR8","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/100803869","volume":"28","author":"G Chapuy","year":"2014","unstructured":"Chapuy G, DeVos M, McDonald J, Mohar B, Scheide D (2014) Packing triangles in weighted graphs. SIAM J Discrete Math 28(1):226\u2013239","journal-title":"SIAM J Discrete Math"},{"key":"859_CR9","doi-asserted-by":"crossref","unstructured":"Chen X, Diao Z, Hu X, Tang Z (2016a) Sufficient conditions for Tuza\u2019s conjecture on packing and covering triangles. Lecture Notes Comput Sci 9843:266\u2013277","DOI":"10.1007\/978-3-319-44543-4_21"},{"key":"859_CR10","doi-asserted-by":"crossref","unstructured":"Chen X, Diao Z, Hu X, Tang Z (2016b) Total dual integrality of triangle covering. Lecture Notes Comput Sci 10043:128\u2013143","DOI":"10.1007\/978-3-319-48749-6_10"},{"issue":"6","key":"859_CR11","doi-asserted-by":"publisher","first-page":"1525","DOI":"10.1007\/s00224-018-9860-7","volume":"62","author":"X Chen","year":"2018","unstructured":"Chen X, Diao Z, Hu X, Tang Z (2018) Covering triangles in edge-weighted graphs. Theory Comput Syst 62(6):1525\u20131552","journal-title":"Theory Comput Syst"},{"issue":"1\u20133","key":"859_CR12","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0012-365X(95)00178-Y","volume":"150","author":"P Erd\u00f6s","year":"1996","unstructured":"Erd\u00f6s P, Gallai T, Tuza Z (1996) Covering and independence in triangle structures. Discrete Math 150(1\u20133):89\u2013101","journal-title":"Discrete Math"},{"issue":"1","key":"859_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0012-365X(98)00183-6","volume":"195","author":"PE Haxell","year":"1999","unstructured":"Haxell PE (1999) Packing and covering triangles in graphs. Discrete Math 195(1):251\u2013254","journal-title":"Discrete Math"},{"issue":"1","key":"859_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s003730050010","volume":"14","author":"PE Haxell","year":"1998","unstructured":"Haxell PE, Kohayakawa Y (1998) Packing and covering triangles in tripartite graphs. Graphs Combin 14(1):1\u201310","journal-title":"Graphs Combin"},{"issue":"1","key":"859_CR15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s004930170003","volume":"21","author":"PE Haxell","year":"2001","unstructured":"Haxell PE, R\u00f6dl V (2001) Integer and fractional packings in dense graphs. Combinatorica 21(1):13\u201338","journal-title":"Combinatorica"},{"key":"859_CR16","doi-asserted-by":"crossref","unstructured":"Haxell P, Kostochka A, Thomass\u00e9 S (2012a) Packing and covering triangles in $$K_4$$-free planar graphs. Graphs Combin 28(5):653\u2013662","DOI":"10.1007\/s00373-011-1071-9"},{"key":"859_CR17","doi-asserted-by":"crossref","unstructured":"Haxell P, Kostochka A, Thomass\u00e9 S (2012b) A stability theorem on fractional covering of triangles by edges. Eur J Combin 33(5):799\u2013806","DOI":"10.1016\/j.ejc.2011.09.024"},{"key":"859_CR18","unstructured":"Hosseinzadeh H, Soltankhah N (2015) Relations between some packing and covering parameters of graphs. In: The 46th Annual Iranian mathematics conference, p 715"},{"issue":"1","key":"859_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0012-365X(93)00228-W","volume":"142","author":"M Krivelevich","year":"1995","unstructured":"Krivelevich M (1995) On a conjecture of Tuza about packing and covering of triangles. Discrete Math 142(1):281\u2013286","journal-title":"Discrete Math"},{"issue":"3","key":"859_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1017\/S0963548397003106","volume":"6","author":"M Krivelevich","year":"1997","unstructured":"Krivelevich M (1997) Triangle factors in random graphs. Combin Probab Comput 6(3):337\u2013347","journal-title":"Combin Probab Comput"},{"issue":"3","key":"859_CR21","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s00373-011-1048-8","volume":"28","author":"SA Lakshmanan","year":"2012","unstructured":"Lakshmanan SA, Bujt\u00e1s C, Tuza Z (2012) Small edge sets meeting all triangles of a graph. Graphs Combin 28(3):381\u2013392","journal-title":"Graphs Combin"},{"key":"859_CR22","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.dam.2015.12.012","volume":"209","author":"A Lakshmanan","year":"2016","unstructured":"Lakshmanan A, Bujt\u00e1s C, Tuza Z (2016) Induced cycles in triangle graphs. Discrete Appl Math 209:264\u2013275","journal-title":"Discrete Appl Math"},{"key":"859_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and computing: randomized algorithms and probabilistic analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher M, Upfal E (2005) Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge"},{"issue":"4","key":"859_CR24","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/s00373-018-1903-y","volume":"34","author":"A Munaro","year":"2018","unstructured":"Munaro A (2018) Triangle packings and transversals of some $$K_4$$-free graphs. Graphs Combin 34(4):647\u2013668","journal-title":"Graphs Combin"},{"key":"859_CR25","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.ejc.2015.03.006","volume":"49","author":"GJ Puleo","year":"2015","unstructured":"Puleo GJ (2015) Tuza\u2019s conjecture for graphs with maximum average degree less than 7. Eur J Combin 49:134\u2013152","journal-title":"Eur J Combin"},{"issue":"7","key":"859_CR26","doi-asserted-by":"publisher","first-page":"1573","DOI":"10.1016\/j.disc.2017.02.020","volume":"340","author":"GJ Puleo","year":"2017","unstructured":"Puleo GJ (2017) Maximal k-edge-colorable subgraphs, Vizing\u2019s theorem, and Tuza\u2019s conjecture. Discrete Math 340(7):1573\u20131580","journal-title":"Discrete Math"},{"issue":"1\u20133","key":"859_CR27","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0012-365X(92)90141-2","volume":"105","author":"A Ruci\u0144ski","year":"1992","unstructured":"Ruci\u0144ski A (1992) Matching and covering the vertices of a random graph by copies of a given graph. Discrete Math 105(1\u20133):185\u2013197","journal-title":"Discrete Math"},{"key":"859_CR28","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-030-64843-5_29","volume":"12577","author":"Z Tang","year":"2020","unstructured":"Tang Z, Diao Z (2020) Packing and covering triangles in dense random graphs. Lecture Notes Comput Sci 12577:426\u2013439","journal-title":"Lecture Notes Comput Sci"},{"key":"859_CR29","unstructured":"Tuza Z (1981) Conjecture. In: Finite and infinite sets, proceedings of Colloquia Mathematica Societatis. Janos Bolyai, p 888"},{"issue":"4","key":"859_CR30","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF01787705","volume":"6","author":"Z Tuza","year":"1990","unstructured":"Tuza Z (1990) A conjecture on triangles of graphs. Graphs Combin 6(4):373\u2013380","journal-title":"Graphs Combin"},{"issue":"6","key":"859_CR31","doi-asserted-by":"publisher","first-page":"952","DOI":"10.1017\/S0963548312000235","volume":"21","author":"R Yuster","year":"2012","unstructured":"Yuster R (2012) Dense graphs with a large triangle cover have a large triangle packing. Combin Probab Comput 21(6):952\u2013962","journal-title":"Combin Probab Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00859-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00859-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00859-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:26:12Z","timestamp":1665779172000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00859-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["859"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00859-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,4,25]]},"assertion":[{"value":"4 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}