Heawood inequalities
type: Item
instance of: scholarly article
title: Heawood inequalities
zbMATH Open document ID: 0628.05029
DOI: 10.1016/0097-3165(87)90076-8
published in: Journal of Combinatorial Theory. Series A
publication date: 1987-01-01T00:00:00Z
review text: The well-known folklore theorem states that any planar graph has a vertex of degree at most five. A generalization of this fact to other surfaces is also known (see, e.g. [\textit{A. T. White}, Graphs, groups and surfaces (Second edition), North Holland (Amsterdam 1984; Zbl 0551.05037)]) and is closely related to the Heawood inequality bounding the chromatic number of a graph embeddable in a closed surface of a given Euler characteristic. The author deals with generalizations of these inequalities to complexes of higher dimensions. Among other results he shows that a simplicial complex K can be embedded in an n-dimensional pseudomanifold \(X^ n\) (n\(\geq 2)\) only if one of its (n-2)-simplices is incident with \(\delta\) (n-1)-simplices where \(\delta <n(n+1)/n-1\) or \[ \left( \begin{matrix} \delta +n-2\\ n\end{matrix} \right)-(2/n+1)\left( \begin{matrix} \delta +n-1\\ n\end{matrix} \right)\leq \dim H_{n-1}(X^ n,Z_ 2)-1. \] For the case of surfaces these are precisely the classical bounds. The methods to establish these inequalities include the fact that Kruskal-Katona simplicial complexes maximize homology.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 57M15
zbMATH DE Number: 4021169
zbMATH Keywords: planar graph
zbMATH Keywords: surfaces
zbMATH Keywords: Heawood inequality
zbMATH Keywords: chromatic number
zbMATH Keywords: simplicial complex
zbMATH Keywords: pseudomanifold
author: Karanbir Singh Sarkaria
MaRDI profile type: Publication
full work available at URL: 0097-3165(87)90076-8
OpenAlex ID: W2913166830
cites work: Every planar map is four colorable. I: Discharging
cites work: Every planar map is four colorable. II: Reducibility
cites work: A simple proof of the Kruskal-Katona theorem
cites work: The chromatic number of a class of pseudo-2-manifolds
cites work: On chromatic number of graphs and set-systems
cites work: Q5720698
cites work: Higher-Dimensional analogs of the four-color problem and some inequalities for simplicial complexes
cites work: Q5584509
cites work: Extremal problems for finite sets and convex hulls---a survey
cites work: Q5726070
cites work: Q4773723
cites work: Q5667781
cites work: On coloring manifolds
cites work: Addendum to may paper ''On coloring manifolds''
cites work: A Trace Formula for Compact Manifolds
cites work: On Neighbourly Triangulations
cites work: An inequality for the chromatic number of a graph
cites work: HYPERGRAPHS
cites work: Q3912613
cites work: Q4014408
cites work: Kneser colorings of polyhedra
description: scientific article; zbMATH DE number 4021169