Some properties of non-bicolorable hypergraphs and the four-color problem
type: Item
instance of: scholarly article
title: Some properties of non-bicolorable hypergraphs and the four-color problem
zbMATH Open document ID: 0851.05080
DOI: 10.1016/0166-218X(95)00028-P
published in: Discrete Applied Mathematics
publication date: 1996-11-21T00:00:00Z
review text: Hypergraphs whose chromatic number is at most 2 are called bicolorable hypergraphs. A non-bicolorable hypergraph which becomes bicolorable when any of its edges (vertices) is removed is called edge-critical (vertex-critical). Edge-critical bicolorable hypergraphs have widely been studied in the literature. In this paper, the author points out that the so far rarely studied vertex-critical hypergraphs have numerous applications, in particular, there is an intimate relationship to the four-colour theorem.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 897373
zbMATH Keywords: bicolorable hypergraphs
zbMATH Keywords: edge-critical
zbMATH Keywords: vertex-critical
zbMATH Keywords: chromatic number
zbMATH Keywords: four-colour theorem
reviewed by: Thomas Andreae
MaRDI profile type: Publication
cites work: On 3-chromatic hypergraphs
cites work: Q4099676
cites work: Optimisation and hypergraph theory
cites work: Q5289274
cites work: Hypergraphs and Ramseyian Theorems
cites work: Q4074927
cites work: On a combinatorial game
cites work: Une classe d'hypergraphes bichromatiques. II
cites work: Q3222234
cites work: Q3879273
cites work: The \(B_r\) property and chromatic numbers of generalized graphs
cites work: ON THE TWO-COLOURING OF HYPERGRAPHS
full work available at URL: 0166-218x(95)00028-p
OpenAlex ID: W2047135167
author: C. Berge
Recommended article: Q4881931
Recommended article: Q4846549
Recommended article: \(P_4\)-colorings and \(P_4\)-bipartite graphs
Recommended article: Q4304330
Recommended article: Q4530616
Recommended article: A 4-colour problem for dense triangle-free graphs
Recommended article: On Some Extremal Properties of Hypergraph Colorings
Recommended article: A note on two-colorability of nonuniform hypergraphs
Recommended article: Q3983109
Recommended article: Quadrangulations and 4-color-critical graphs
description: scientific article; zbMATH DE number 897373