Local chromatic number and distinguishing the strength of topological obstructions

DOI10.1090/S0002-9947-08-04643-6MaRDI QIDQ3605849zbMATH OpenOpenAlexFDO

Authors Gábor Simonyi, Gábor Tardos, Siniša T. Vrećica

Publication date 25 February 2009

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0502452

zbMATH Keywords

Borsuk-Ulam theorem box complex local chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Relations of low-dimensional topology with graph theory (57M15)

Abstract: The local chromatic number of a graph G is the number of colors appearing in the most colorful closed neighborhood of a vertex minimized over all proper colorings of G. We show that two specific topological obstructions that have the same implications for the chromatic number have different implications for the local chromatic number. These two obstructions can be formulated in terms of the homomorphism complex Hom(K_2,G) and its suspension, respectively. These investigations follow the line of research initiated by Matousek and Ziegler who recognized a hierarchy of the different topological expressions that can serve as lower bounds for the chromatic number of a graph. Our results imply that the local chromatic number of 4-chromatic Kneser, Schrijver, Borsuk, and generalized Mycielski graphs is 4, and more generally, that 2r-chromatic versions of these graphs have local chromatic number at least r+2. This lower bound is tight in several cases by results in an earlier paper of the first two authors.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Local chromatic number and distinguishing the strength of topological obstructions

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