Alexander Engström: Polynomially chi-bounded graph classes from vanishing syzygies of edge ideals

Abstract: Perfect graphs are characterized by that the chromatic number equals the order of the largest clique for every induced subgraph. The last years have seen a tremendous progress in natural relaxation of perfectness. A graph class is called chi-bounded if the chromatic number is bounded from above by a function of the order of the largest clique. Sometimes the function is even polynomial. The edge ideal of a graph is in a ring whose indeterminants correspond to the vertices of the graph and the generators of the ideal are products of pairs of indeterminants that are adjacent in the graph. There are bigraded betti numbers measuring the dimension of the syzygies at position (i,j) in the resolution of an ideal. We study the graph classes where the syzygies of the edge ideals vanish for some bigrading (i,j). We show that such classes are chi-bounded by a polynomial of degree 2(j-i-2).