The χ-binding function of d-directional segment graphs
Time: 14:00 -- Location: LRI, 445
summary: To color a graph properly, one needs at least as many colors as the size of its biggest clique; therefore,
the chromatic number χ is lower-bounded by the clique number ω. In general, there are no upper bounds on χ in terms
of ω. The graphs for which we can approximate the chromatic number with ω ≤ χ ≤ f(ω) for some function f are called
χ-bounded graphs and the optimal function f is called the χ-binding function.
A class of graphs that has been the object of many studies in structural graph theory is the class of segment graphs:
a segment graph is formed by a collection of straight line segments in the plane where the vertices are the segments
and there is an edge between two intersecting segments. If the segments are all parallel, then it is also called an
interval graph, known for being perfect (χ = ω). In the 70s, Erdös asked if we allow segments to have different slopes,
then can we still approximate χ with ω, i.e. are segment graphs χ-bounded? In 2014, Pawlik, Kozik, Krawczyk, Lasón,
Micek, Trotter, and Walczak showed a construction of a triangle-free graph (ω = 2) with arbitrarily large chromatic
number, answering Erdös question in the negative.
However, if one only allows the segments to have d different slopes (d-directional segment graphs), then it is easy
to color the graph with dω colors since each slope induces an interval graph. Bhattacharya, Dvorák and Noorizadeh
conjectured that dω is optimal, meaning that there exists d-directional segment graphs for which χ = dω for every d
and every ω.
In this seminar, we will show the χ-binding function of d-directional segment graphs, which confirms the conjecture
for even ω and refutes it for odd ω.