Lethbridge Number Theory and Combinatorics Seminar: Muhammad Khan

The relationship between independence number, chromatic number, clique number, clique cover number and their fractional analogues is well-established for perfect graphs. Here, we study the clique k-cover number cck(G) and the fractional clique k-cover number ccfk(G) of a graph G. We relate ccfk(G) to the fractional chromatic number of the complement G ̅ , obtaining a Nordhaus–Gaddum type result. We modify the method of Kahn and Seymour, used in the proof of the fractional Erdős–Faber–Lovász conjecture, to derive an upper bound on ccfk(G) in terms of the independence number α(G′) of a particular induced subgraph G′ of G. When G is perfect, we get the sharper relation ccfk(G)=kcc1(G)=kα(G)≤cck(G). This is in line with a result of Grötschel, Lovász, and Schrijver on clique covers of perfect graphs. Moreover, we derive an upper bound on the fractional chromatic number of any graph, which is tight for infinitely many perfect as well as non-perfect graphs. This is joint work with Daya Gaur (Lethbridge). *Please refer to the main page for appropriate equations.