Independent sets, cliques, and colorings in graphons

0494641 - ÚI 2019 US eng V - Výzkumná zpráva
Hladký, J. - Rocha, Israel
Independent sets, cliques, and colorings in graphons.
Cornell University, 2017. 17 s. arXiv.org e-Print archive, arXiv:1712.07367 [math.CO], accepted to European Journal of Combinatorics.
Grant CEP: GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: Graph limits * Perfect Graphon * Chromatic number * Fractional Chromatic number * clique number * independence number
Obor OECD: Pure mathematics
https://arxiv.org/abs/1712.07367

We study graphon counterparts of the chromatic and the clique number, the fractional chromatic number, the b-chromatic number, and the fractional clique number. We establish some basic properties of the independence set polytope in the graphon setting, and duality properties between the fractional chromatic number and the fractional clique number. We present a notion of perfect graphons and characterize them in terms of induced densities of odd cycles and its complements.
Trvalý link: http://hdl.handle.net/11104/0287750