Local chromatic number, Ky Fan's theorem, and circular colorings (Q879165): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Gábor Simonyi / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Gábor Tardos / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1963931974 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0407075 / rank | |||
Normal rank |
Latest revision as of 18:30, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Local chromatic number, Ky Fan's theorem, and circular colorings |
scientific article |
Statements
Local chromatic number, Ky Fan's theorem, and circular colorings (English)
0 references
8 May 2007
0 references
For any proper coloring \(c\) of a graph \(G\), let \(n(c,v)\) be the number of colors appearing within distance 1 of vertex \(v\) in \(G\). The local chromatic number of \(G\) is defined as the minimum over \(c\) of the maximum over \(v\) of \(n(c,v)\). The local chromatic number is bounded above by the chromatic number and below by the fractional chromatic number. Using topological results by Borsuk-Ulam and Ky Fan, the local chromatic number is studied for many cases when there is a large gap between the chromatic and the fractional chromatic numbers.
0 references
chromatic numbers
0 references
Kneser graphs
0 references
Schrijver graphs
0 references
Mycielski graphs, Borsuk graphs
0 references