| Monday, October 7th, 2013 | 4:00pm-5:00pm | Burnside 1205 |
For a graph G, let #E(G) be the number of stable sets of even size and let #O(G) be the number of stable sets of odd size. We are interested in the relation between the structure of a graph and the value of |#E(G)-#O(G)|. As it turns out, |#E(G)-#O(G)| has small value in many natural situations, and the simplest examples where |#E(G)-#O(G)| is larger than 1 are complete graphs, and cycles of length divisible by 3. Kalai and Meshulam made a conjecture that if |#E(H)-#O(H)| is bounded for all induced subgraphs H of G, then the chromatic number of G is bounded; they also conjectured that if G has no induced cycle of length divisible by 3, then G has bounded chromatic number. These two conjectures lead us to study the following question: is it true that if a graph G has no induced cycle of length divisible by 3, then |#E(G)-#O(G)| is at most one? In this talk we discuss a special case of this problem, and give a complete structural description of graphs with no cycle o f length divisible by 3 (not necessarily induced). The proof of the conjecture in this special case follows directly from the results of the decomposition. Joint work with Maria Chudnovsky, Alex Scott and Paul Seymour.