Color-critical graphs and hypergraphs with few edges and no short cycles
type: Item
instance of: scholarly article
title: Color-critical graphs and hypergraphs with few edges and no short cycles
zbMATH Open document ID: 0893.05003
DOI: 10.1016/S0012-365X(97)00137-4
author: J. Ning
published in: Discrete Mathematics
publication date: 1998-02-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1121481
zbMATH Keywords: hypergraph
zbMATH Keywords: coloring
zbMATH Keywords: color-critical graphs
zbMATH Keywords: cycles
reviewed by: Andreas Huck
MaRDI profile type: Publication
cites work: On A Combinatorial Problem of Erdös
cites work: Sparse colour-critical hypergraphs
cites work: Sparse color‐critical graphs and hypergraphs with no short cycles
cites work: The existence problem for colour critical linear hypergraphs
cites work: Q4291347
cites work: Q4141279
cites work: On chromatic number of graphs and set-systems
cites work: ON THE TWO-COLOURING OF HYPERGRAPHS
cites work: Distributed density estimation in sensor networks based on variational approximations
cites work: Q3922685
full work available at URL: s0012-365x(97)00137-4
OpenAlex ID: W2024717990
description: scientific article; zbMATH DE number 1121481