This event is from the archives of The Notice Board. The event has already taken place and the information contained in this post may no longer be relevant or accurate.
Lethbridge Number Theory and Combinatorics Seminar
Date:
October 15, 2018
Time:
Noon to 12:50 p.m.
Lecturer(s):
Muhammad Khan (University of Lethbridge)
Location:
University of Lethbridge
Topic:
Fractional clique k-covers, vertex colorings and perfect graphs
Description:
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 cc_k(G) and the fractional clique k-cover number cc_fk(G) of a graph G. We relate cc_fk(G) to the fractional chromatic number of the complement of G, obtaining a Nordhaus-Gaddum type result. We modify the method of Kahn and Seymour, used in the proof of the fractional Erdos-Faber-Lovasz conjecture, to derive an upper bound on cc_fk(G) in terms of the independence number alpha(G') of a particular induced subgraph G' of G. When G is perfect, we get the sharper relation cc_fk(G)= k cc_1(G)= k alpha(G) < cc_k(G) + 1. This is in line with a result of Grotschel, Lovasz, 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).
Other Information:
Location: C630 University Hall
Contact:
Barb Hodgson | hodgsonb@uleth.ca | (403) 329-2470 | uleth.ca/artsci/math-computer-science
