Seminar of Algorithms of Saclay Plateau: Hoang La on Friday 10 November 2023 at 14h00 ===== Seminar "Algorithms of Saclay Plateau" ===== Dear all, Reminder: Recall that next seminar will be on Wednesday 31 January 2024 at 10h30 by Hang Zhou: Capacitated Vehicle Routing. Notce that for another seminar of the seminar "Algorithms of Saclay Plateau", we are happy to welcome Hoang La. ***** Friday 10 November 2023 at 14h00, room (TBA) ***** Hoang La -- The χ-binding function of d-directional segment graphs 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 ω. Following seminars: TBA The list of next seminars can be found at: https://bournez.gitlabpages.inria.fr/seminar-algorithms-plateau-Saclay/seminar/ The calendar of seminars can be found at: https://bournez.gitlabpages.inria.fr/seminar-algorithms-plateau-Saclay/seminar.ics