Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Local chromatic number and topology

Abstract : The local chromatic number of a graph, introduced by Erdős et al., is the minimum number of colors that must appear in the closed neighborhood of some vertex in any proper coloring of the graph. This talk would like to survey some of our recent results on this parameter. We give a lower bound for the local chromatic number in terms of the lower bound of the chromatic number provided by the topological method introduced by Lovász. We show that this bound is tight in many cases. In particular, we determine the local chromatic number of certain odd chromatic Schrijver graphs and generalized Mycielski graphs. We further elaborate on the case of $4$-chromatic graphs and, in particular, on surface quadrangulations.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:58:48 PM
Last modification on : Tuesday, November 26, 2019 - 4:12:08 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:11:54 AM


Publisher files allowed on an open archive




Gábor Simonyi, Gábor Tardos. Local chromatic number and topology. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.375-378, ⟨10.46298/dmtcs.3447⟩. ⟨hal-01184436⟩



Record views


Files downloads