Independent sets, cliques, and colorings in graphons. (August 2020)

• Record Type: Journal Article
• Authors: Hladký, Jan; Rocha, Israel
• Is Part Of: European journal of combinatorics. Volume 88(2020)
• Publication Date: 2020-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103108
• Languages: English
• ISSNs: 0195-6698

Abstract

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.