{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T14:10:07Z","timestamp":1744207807470,"version":"3.37.3"},"reference-count":6,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2017-19\/2017"],"award-info":[{"award-number":["LP2017-19\/2017"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Research, Development and Innovation Office \u2013 NKFIH","award":["K 132696"],"award-info":[{"award-number":["K 132696"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give a characterization of finite sets of triples of elements (e.g., positive integers) that can be colored with two colors such that for every element <jats:italic>i<\/jats:italic> in each color class there exists a triple which does not contain <jats:italic>i<\/jats:italic>. We give a linear (in the number of triples) time algorithm to decide if such a coloring exists and find one if it does. We also consider generalizations of this result and an application to a matching problem, which motivated this study. Finally, we show how these results translate to results about colorings of hypergraphs in which the degree of every vertex is <jats:italic>k<\/jats:italic> less than the number of hyperedges.<\/jats:p>","DOI":"10.1007\/s00373-020-02217-1","type":"journal-article","created":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T15:04:16Z","timestamp":1596726256000},"page":"1783-1795","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Two-Coloring Triples such that in Each Color Class Every Element is Missed at Least Once"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3839-5103","authenticated-orcid":false,"given":"Bal\u00e1zs","family":"Keszegh","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,6]]},"reference":[{"key":"2217_CR1","unstructured":"9th Eml\u00e9kt\u00e1bla workshop booklet, https:\/\/www.renyi.hu\/~emlektab\/index.html. Accessed 28 July 2020"},{"issue":"1","key":"2217_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.03.038","volume":"254","author":"T Januario","year":"2016","unstructured":"Januario, T., Urrutia, S., Ribeiro, C.C., de Werra, D.: Edge coloring: a natural model for sports scheduling. Eur. J. Oper. Res. 254(1), 1\u20138 (2016)","journal-title":"Eur. J. Oper. Res."},{"key":"2217_CR3","unstructured":"Cechl\u00e1rov\u00e1, K., Jank\u00f3, Zs., Salia, N.: personal communication (2019)"},{"issue":"1","key":"2217_CR4","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.cor.2010.04.012","volume":"38","author":"R Lewis","year":"2011","unstructured":"Lewis, R., Thompson, J.: On the application of graph colouring techniques in round-robin sports scheduling. Comput. Oper. Res. 38(1), 190\u2013204 (2011)","journal-title":"Comput. Oper. Res."},{"key":"2217_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness.","author":"Michael R Garey","year":"1979","unstructured":"Garey, Michael R., Johnson, David S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., London (1979). ISBN 0716710447"},{"key":"2217_CR6","unstructured":"Lov\u00e1sz, L\u00e1szl\u00f3: Coverings and colorings of hypergraphs. In: Proceedings of 4th southeastern conference on Comb., Utilitas Math., pp. 3\u201312 (1973)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02217-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-020-02217-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02217-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T23:40:06Z","timestamp":1628206806000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-020-02217-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,6]]},"references-count":6,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["2217"],"URL":"https:\/\/doi.org\/10.1007\/s00373-020-02217-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2020,8,6]]},"assertion":[{"value":"6 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}