Color-critical graphs and hypergraphs with few edges and no short cycles (Q1379816): Difference between revisions

An \(r\)-coloring of a hypergraph \((V, {\mathcal G})\) with vertex set \(V\) and edge set \({\mathcal G}\) is a coloring of its vertices with at most \(r\) colors such that each edge is incident with at least two vertices of different colors. \((V, {\mathcal G})\) is \(r\)-chromatic if \(r\) is the smallest integer for which \((V, {\mathcal G})\) is \(r\)-colorable (i.e. \((V, {\mathcal G})\) has an \(r\)-coloring). If additionally, \((V,{\mathcal G} \setminus \{E\})\) is not \(r\)-colorable for each \(E\in {\mathcal G}\), then \((V, {\mathcal G})\) is called color-critical if \((V, {\mathcal G})\) is \(r\)-critical for some integer \(r\). In the present paper, the authors introduce new constructions of color-critical hypergraphs which are partially based on Hajós' classical construction of color-critical graphs. For each \(r\geq 2\) and \(n\geq 2\), they obtain large \(r\)-critical hypergraphs with relatively few edges in which each edge is incident with exactly \(n\) vertices (we have ordinary graphs if \(n=2)\) and which do not contain cycles of length less than 6. Here a cycle of length \(\ell\) is an alternating sequence \(v_0F_1v_1F_2v_2 \dots F_{\ell-1} v_{\ell-1} F_\ell v_\ell =v_0\) with distinct vertices \(v_0, \dots, v_{\ell-1}\) and distinct edges \(F_1, \dots, F_\ell\) such that any two consecutive elements in the sequence are incident.