Title: The Structure of Graphs with No Cycles of Length Divisible by Three
Speaker: Matthieu Plumettaz, Columbia University
Date: Tuesday, November 5, 2013 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math