Open Collections

Description

The local chromatic number of a graph is a coloring invariant introduced in 1986 by Erd ̋os, Fu ̈redi, Hajnal, Komj ́ath, R ̈odl, and Seress. In 2005 with K ̈orner and Pilotto we observed that it is bounded from below by the fractional chromatic number. This observation triggered a more systematic study of the local chromatic number for graphs that have a large gap between their chromatic number and fractional chromatic number. Such graphs are rare and usually have remarkable properties. With K ̈orner and Pilotto we also introduced a directed version of the local chromatic number to bound Sperner capacity from above. Recently, due to work by Shanmugam, Dimakis, and Langberg, it turned out to also have some relevance in index coding. This talk is planned to be a survey of results found in the last decade about the local chromatic number and its directed version. Even though there is the above mentioned connection with index coding this talk cannot claim to give direct applications of the results in it to network coding. It should rather be considered as a talk about an interesting topic, some knowledge about which may or may not become useful in the future in the network coding context. The results to be presented are joint with di↵erent subsets of the following co-autors: J ́anos K ̈orner, Bojan Mohar, Concetta Pilotto, G ́abor Tardos, Sinivsa Vre ́cica, Ambrus Zsb ́an.