The structure of graphs with no cycles of length divisible by three

Thursday, September 12, 2013 -
4:30pm to 6:00pm
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 of 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.
Speaker: 
Matthieu Plumettaz
Columbia University
Event Location: 
Fine Hall 224