{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T07:11:04Z","timestamp":1696403464039},"reference-count":20,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2014,12,10]],"date-time":"2014-12-10T00:00:00Z","timestamp":1418169600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"Natinal Research Foundation; University of Johannesburg","award":["No Grant Number"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2015,10]]},"abstract":"Abstract<\/jats:title>In this article, we continue the study of 2\u2010colorings in hypergraphs. A hypergraph is 2\u2010colorable if there is a 2\u2010coloring of the vertices with no monochromatic hyperedge. Let denote the class of all k<\/jats:italic>\u2010uniform k<\/jats:italic>\u2010regular hypergraphs. It is known (see Alon and Bregman [Graphs Combin. 4 (1988) 303\u2013306] and Thomassen [J. Amer. Math. Soc. 5 (1992), 217\u2013229] that every hypergraph is 2\u2010colorable, provided . As remarked by Alon and Bregman the result is not true when , as may be seen by considering the Fano plane. Indeed there are several constructions for building infinite families of hypergraphs in that are not 2\u2010colorable. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set X<\/jats:italic> of vertices in a hypergraph H<\/jats:italic> to be a free set in H<\/jats:italic> if we can 2\u2010color such that every edge in H<\/jats:italic> receives at least one vertex of each color. We conjecture that for , every hypergraph has a free set of size in\u00a0H<\/jats:italic>. We show that the bound cannot be improved for any and we prove our conjecture when . Our proofs use results from areas such as transversal in hypergraphs, cycles in digraphs, and probabilistic arguments.<\/jats:p>","DOI":"10.1002\/jgt.21843","type":"journal-article","created":{"date-parts":[[2014,12,10]],"date-time":"2014-12-10T13:23:24Z","timestamp":1418217804000},"page":"112-135","source":"Crossref","is-referenced-by-count":2,"title":["On 2\u2010Colorings of Hypergraphs"],"prefix":"10.1002","volume":"80","author":[{"given":"Michael A.","family":"Henning","sequence":"first","affiliation":[{"name":"DEPARTMENT OF MATHEMATICS UNIVERSITY OF JOHANNESBURG AUCKLAND PARK JOHANNESBURG 2006 SOUTH AFRICA"}]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[{"name":"ENGINEERING SYSTEMS AND DESIGN SINGAPORE UNIVERSITY OF TECHNOLOGY AND DESIGN 20 DOVER DRIVE, SINGAPORE 138682 SINGAPORE"}]}],"member":"311","published-online":{"date-parts":[[2014,12,10]]},"reference":[{"key":"e_1_2_5_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.004"},{"key":"e_1_2_5_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.09.001"},{"key":"e_1_2_5_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01864169"},{"key":"e_1_2_5_5_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/jcd.20073","article-title":"Note on disjoint blocking sets in Galois planes","volume":"14","author":"Ba\u0155at J.","year":"2005","journal-title":"J Combin Designs"},{"key":"e_1_2_5_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0121041"},{"key":"e_1_2_5_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00182909"},{"key":"e_1_2_5_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00151351"},{"key":"e_1_2_5_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01191201"},{"key":"e_1_2_5_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20340"},{"key":"e_1_2_5_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/100802463"},{"key":"e_1_2_5_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.04.005"},{"key":"e_1_2_5_13_1","unstructured":"1998 Oxford University Press Oxford J. W. P. Hirschfeld Projective Geometries over Finite Fields xiv 555"},{"key":"e_1_2_5_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(13)80101-1"},{"key":"e_1_2_5_15_1","article-title":"Proof of a conjecture of Henning and Yeo on vertex\u2010disjoint directed cycles","author":"Lichiardopol N.","journal-title":"SIAM J Discrete Math"},{"key":"e_1_2_5_16_1","first-page":"206","article-title":"Theory of Graphs","volume":"38","author":"Ore O.","year":"1962","journal-title":"Amer. Math. Soc. Transl"},{"key":"e_1_2_5_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/25.1.303"},{"key":"e_1_2_5_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2020-3"},{"key":"e_1_2_5_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579195"},{"key":"e_1_2_5_20_1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1090\/S0894-0347-1992-1135027-1","article-title":"The even cycle problem for directed graphs","volume":"5","author":"Thomassen C.","year":"1992","journal-title":"J Amer Math Soc"},{"key":"e_1_2_5_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90354-K"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.21843","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.21843","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T20:21:34Z","timestamp":1696364494000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.21843"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,10]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["10.1002\/jgt.21843"],"URL":"https:\/\/doi.org\/10.1002\/jgt.21843","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,10]]}}}