Thursday, July 30th, 2026
2:00pm – 2:50pm
Stratton Hall 313
Speaker: Martin Milanič, University of Primorska, Slovenia
Title: Linear colorings of graphs
Abstract: How many colors are needed to color the vertices of a graph so that each connected subgraph admits a color that appears exactly once? What if this requirement is relaxed to paths only? The corresponding two graph parameters were studied in the literature under different names, including centered and linear chromatic number, respectively. In 2021, Kun, O'Brien, Pilipczuk, and Sullivan proved that the two parameters are polynomially related and conjectured that they never differ more than by a factor of 2. We investigate the properties of linear chromatic number and provide improved bounds in several graph classes.
Joint work with Claire Hilaire (Clermont-Auvergne), Matjaž Krnc (Primorska) and Jean-Florent Raymond (CNRS, ENS de Lyon).