Systolic inequalities and chromatic number

Publication date 31 October 2022

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Metric geometry (51F99)

Abstract: We show that the discrete versions of the systolic inequality that estimate the number of vertices of a simplicial complex from below have substantial applications to graphs, the one-dimensional simplicial complexes. Almost directly they provide good estimates for the number of vertices of a graph in terms of its chromatic number and the length of the smallest odd cycle. Combined with the graph-theoretic techniques of Berlov and Bogdanov, the systolic approach produces even better estimates.

This page was built for publication: Systolic inequalities and chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6415604)