{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T14:50:09Z","timestamp":1767970209979,"version":"3.49.0"},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2012,4,20]],"date-time":"2012-04-20T00:00:00Z","timestamp":1334880000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>A colouring of the vertices of a hypergraph <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548312000156_char1\"\/><\/jats:private-char> is called <jats:italic>conflict-free<\/jats:italic> if each edge <jats:italic>e<\/jats:italic> of <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548312000156_char1\"\/><\/jats:private-char> contains a vertex whose colour does not repeat in <jats:italic>e<\/jats:italic>. The smallest number of colours required for such a colouring is called the conflict-free chromatic number of <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548312000156_char1\"\/><\/jats:private-char>, and is denoted by \u03c7<jats:sub><jats:italic>CF<\/jats:italic><\/jats:sub>(<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548312000156_char1\"\/><\/jats:private-char>). Pach and Tardos proved that for an (2<jats:italic>r<\/jats:italic> \u2212 1)-uniform hypergraph <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548312000156_char1\"\/><\/jats:private-char> with <jats:italic>m<\/jats:italic> edges, \u03c7<jats:sub>CF<\/jats:sub>(<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548312000156_char1\"\/><\/jats:private-char>) is at most of the order of <jats:italic>rm<\/jats:italic><jats:sup>1\/<jats:italic>r<\/jats:italic><\/jats:sup> log <jats:italic>m<\/jats:italic>, for fixed <jats:italic>r<\/jats:italic> and large <jats:italic>m<\/jats:italic>. They also raised the question whether a similar upper bound holds for <jats:italic>r<\/jats:italic>-uniform hypergraphs. In this paper we show that this is not necessarily the case. Furthermore, we provide lower and upper bounds on the minimum number of edges of an <jats:italic>r<\/jats:italic>-uniform simple hypergraph that is not conflict-free <jats:italic>k<\/jats:italic>-colourable.<\/jats:p>","DOI":"10.1017\/s0963548312000156","type":"journal-article","created":{"date-parts":[[2012,4,20]],"date-time":"2012-04-20T09:30:45Z","timestamp":1334914245000},"page":"611-622","source":"Crossref","is-referenced-by-count":13,"title":["Conflict-Free Colourings of Uniform Hypergraphs With Few Edges"],"prefix":"10.1017","volume":"21","author":[{"given":"A.","family":"KOSTOCHKA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"KUMBHAT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"\u0141UCZAK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,4,20]]},"reference":[{"key":"S0963548312000156_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/1383369.1383375"},{"key":"S0963548312000156_ref10","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300006069"},{"key":"S0963548312000156_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446682"},{"key":"S0963548312000156_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1162-6"},{"key":"S0963548312000156_ref2","doi-asserted-by":"crossref","unstructured":"[2] Alon N. and Smorodinsky S. (2006) Conflict-free colorings of shallow discs. In 22nd Annual ACM Symposium on Computational Geometry, pp. 41\u201343.","DOI":"10.1145\/1137856.1137864"},{"key":"S0963548312000156_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990290"},{"key":"S0963548312000156_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55566-4_30"},{"key":"S0963548312000156_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2"},{"key":"S0963548312000156_ref7","first-page":"609","volume-title":"Infinite and Finite Sets","author":"Erd\u0151s","year":"1975"},{"key":"S0963548312000156_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702431840"},{"key":"S0963548312000156_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(81)90045-5"},{"key":"S0963548312000156_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90191-7"},{"key":"S0963548312000156_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582966"},{"key":"S0963548312000156_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13580-4_9"},{"key":"S0963548312000156_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_21"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T19:47:42Z","timestamp":1556221662000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000156\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,20]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["S0963548312000156"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000156","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,20]]}}}