Independent sets, cliques, and colorings in graphons

0494641 - ÚI 2019 US eng V - Research Report
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.
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : Graph limits * Perfect Graphon * Chromatic number * Fractional Chromatic number * clique number * independence number
OECD category: 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.
Permanent Link: http://hdl.handle.net/11104/0287750