{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,17]],"date-time":"2024-07-17T13:07:59Z","timestamp":1721221679964},"reference-count":12,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2009,10,20]],"date-time":"2009-10-20T00:00:00Z","timestamp":1255996800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2010,6]]},"abstract":"Abstract<\/jats:title>Let \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${\\mathcal{H}}=({{X}},{\\mathcal{E}})$\\end{document}<\/jats:styled-content> be a hypergraph with vertex set X<\/jats:italic> and edge set \n\\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${\\mathcal{E}}$\\end{document}<\/jats:styled-content>. A C\u2010coloring of \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${\\mathcal{H}}$\\end{document}<\/jats:styled-content> is a mapping \u03d5<\/jats:italic>:X<\/jats:italic>\u2192\u2115 such that |\u03d5<\/jats:italic>(E<\/jats:italic>)|<|E<\/jats:italic>| holds for all edges \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${{E}}\\in{\\mathcal{E}}$\\end{document}<\/jats:styled-content> (i.e. no edge is multicolored). We denote by \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}$\\bar{\\chi}({\\mathcal{H}})$\\end{document}<\/jats:styled-content> the maximum number |\u03d5<\/jats:italic>(X<\/jats:italic>)| of colors in a C\u2010coloring. Let further \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}$\\alpha({\\mathcal{H}})$\\end{document}<\/jats:styled-content> denote the largest cardinality of a vertex set S<\/jats:italic>\u2286X<\/jats:italic> that contains no \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${{E}}\\in{\\mathcal{E}}$\\end{document}<\/jats:styled-content>, and \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}$\\tau({\\mathcal{H}})=|{{X}}|-\\alpha({\\mathcal{H}})$\\end{document}<\/jats:styled-content> the minimum cardinality of a vertex set meeting all \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document} $E \\in {\\mathcal{E}}$\\end{document}<\/jats:styled-content>. The hypergraph \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document} ${\\mathcal{H}}$\\end{document}<\/jats:styled-content> is called C\u2010perfect if \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document} $\\bar{\\chi}({\\mathcal{H}}\\prime)=\\alpha({\\mathcal{H}}\\prime)$\\end{document}<\/jats:styled-content> holds for every induced subhypergraph \n\\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${\\mathcal{H}}\\prime\\subseteq{\\mathcal{H}}$\\end{document}<\/jats:styled-content>. If \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${\\mathcal{H}}$\\end{document}<\/jats:styled-content> is not C\u2010perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C\u2010imperfect. We prove that for all r, k<\/jats:italic>\u2208\u2115 there exists a finite upper bound h<\/jats:italic>(r, k<\/jats:italic>) on the number of minimally C\u2010imperfect hypergraphs \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}${\\mathcal{H}}$\\end{document}<\/jats:styled-content> with \\documentclass{article}\\footskip=0pc\\pagestyle{empty}\\begin{document}$\\tau({\\mathcal{H}})\\le {{k}}$\\end{document}<\/jats:styled-content> and without edges of more than r<\/jats:italic> vertices. We give a characterization of minimally C\u2010imperfect hypergraphs that have \u03c4=2, which also characterizes implicitly the C\u2010perfect ones with \u03c4=2. From this result we derive an infinite family of new constructions that are minimally C\u2010imperfect. A characterization of minimally C\u2010imperfect circular hypergraphs is presented, too. \u00a9 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132\u2013149, 2010<\/jats:p>","DOI":"10.1002\/jgt.20444","type":"journal-article","created":{"date-parts":[[2009,10,20]],"date-time":"2009-10-20T20:50:03Z","timestamp":1256071803000},"page":"132-149","source":"Crossref","is-referenced-by-count":6,"title":["C\u2010perfect hypergraphs"],"prefix":"10.1002","volume":"64","author":[{"given":"Csilla","family":"Bujt\u00e1s","sequence":"first","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2009,10,20]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Hypergraphs","author":"Berge C.","year":"1989"},{"key":"e_1_2_1_3_2","unstructured":"Cs.Bujt\u00e1sandZs.Tuza Voloshin's conjecture for C\u2010perfect hypertrees(manuscript 2007)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)89209-8"},{"key":"e_1_2_1_5_2","first-page":"181","article-title":"On the maximal number of edges representing the edges of a graph","volume":"6","author":"Erd\u0151s P.","year":"1961","journal-title":"Magyar Tud Akad Mat Kut Int K\u00f6zl"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(82)90065-X"},{"key":"e_1_2_1_7_2","first-page":"25","article-title":"A counter\u2010example to Voloshin's hypergraph co\u2010perfectness conjecture","volume":"27","author":"Kr\u00e1l' D.","year":"2003","journal-title":"Australasian J Combin"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90045-7"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580235"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90043-7"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90064-2"},{"key":"e_1_2_1_12_2","first-page":"25","article-title":"On the upper chromatic number of a hypergraph","volume":"11","author":"Voloshin V. I.","year":"1995","journal-title":"Australasian J Combin"},{"key":"e_1_2_1_13_2","volume-title":"Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, Fields Institute Monograph","author":"Voloshin V. I.","year":"2002"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.20444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.20444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,2]],"date-time":"2023-11-02T04:28:37Z","timestamp":1698899317000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.20444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,20]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1002\/jgt.20444"],"URL":"https:\/\/doi.org\/10.1002\/jgt.20444","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,20]]}}}