2025/12/25 by Alexander Engström, Engström, Alexander
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #FOS: Mathematics #Polynomial and algebraic computation
paper · doi:10.48550/arxiv.2512.21800
openalex publication_date 2025/12/25 · openalex created_date 2025/12/30 · openalex updated_date 2026/07/28
The chromatic number χ of a graph is bounded from below by its clique number ω, but it can be arbitrary large. Perfect graphs are defined by χ=ω for all induced subgraphs. An interesting relaxation are χ-bounded graph classes, where χ≤ f(ω). It is not always possible to achieve this with a polynomial f. The edge ideal IG of a graph G is generated by monomials xuxv for each edge uv of G. The bi-graded betti numbers βi,j(I) are central algebraic geometric invariants. We study the graph classes where for some fixed i,j that syzygy vanishes, that is, βi,j(IG)=0. We prove that χ≤ f(ω), where f is a polynomial of degree 2j-2i-4. For the elementary special case βi,2i+2(IG)=0, this amounts to that (i+1)K2-free graphs are ω-1+2i \choose 2i-colorable, improving on an old combinatorial result by Wagon. We also show that triangle-free graphs with βi,j(IG)=0 are (j-1)-colorable. Complexity wise, we show that these colorings can be derived in time O(n3) for graphs on n vertices. Moreover, we show that for almost all graphs with parabolic i,j, there are better bounds on χ.