Coloring Superstable Graphs

שלחו לחבר
Yatir Halevi (BGU)
12/10/2020 - 13:00 - 11:00

Given a graph G=(V,E), a coloring of G in \kappa colors is a map c:V\to \kappa in which adjacent vertices are colored in different colors. The chromatic number of G is the smallest such \kappa.

We will briefly review some questions and conjectures on the chromatic number of infinite graphs and will mainly concentrate on the following strong form of Taylor's conjecture:
If G is an infinite graph with chromatic number\geq \alepha_1 then it contains all finite subgraphs of Sh_n(\omega) for some n, where Sh_n(\omega) is the n-shift graph (which we will introduce).

The conjecture was disproved by Hajnal-Komjath. However, we will present a proof for \omega-stable graphs and a proof of a generalization for superstable graphs. If time permits will discuss stable graphs in general.
No previous knowledge in model theory or graph theory is needed.

Joint work with Itay Kaplan and Saharon Shelah.