Independent sets, cliques, and colorings in graphons

Abstract

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.

18 pages, accepted to European Journal of Combinatorics (special issue Eurocomb 2017)

References in corpus (3)

• Cliques in dense inhomogeneous random graphs
• Komlós's tiling theorem via graphon covers
• Matching polytons

Cited by in corpus (8)

• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Tilings in graphons
• Matching polytons
• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
• Generalizing Körner's graph entropy to graphons
• On the chromatic number in the stochastic block model
• On the chromatic number of graphons
• The dual Cheeger-Buser inequality for graphons