20.500.12556/RUP-22852 Linear colorings of graphs Motivated by algorithmic applications, Kun, O’Brien, Pilipczuk, and Sullivan introduced the parameter linear chromatic number as a relaxation of treedepth and proved that the two parameters are polynomially related. They conjectured that treedepth could be bounded from above by twice the linear chromatic number. In this paper we investigate the properties of linear chromatic number and provide improved bounds in several graph classes. Motivirani z algoritmičnimi aplikacijami so Kun, O’Brien, Pilipczuk in Sullivan uvedli parameter linearno kromatično število kot relaksacijo drevesne globine in dokazali, da sta ta dva parametra polinomsko povezana. Postavili so domnevo, da je drevesno globino mogoče navzgor omejiti z dvakratnikom linearnega kromatičnega števila. V članku raziskujemo lastnosti linearnega kromatičnega števila in podamo izboljšane meje za več razredov grafov. linear coloring central coloring treedepth linearno barvanje središčno barvanje drevesna globina true false false Angleški jezik Slovenski jezik Neznano 2026-03-25 10:05:24 2026-03-25 10:05:24 2026-03-26 03:08:58 0000-00-00 00:00:00 2026 0 0 str. 1-22 [article no.] ǂ104374 Vol. 135 May 2026 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2026-05-01 2028-03-23 519.17 0195-6698 10.1016/j.ejc.2026.104374 272926979 https://www.sciencedirect.com/science/article/pii/S0195669826000429?via%3Dihub 1 bbaaa6ab-2829-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33345 https://arxiv.org/abs/2505.02768 1 bbe313ff-2829-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33346 RAZ_Hilaire_Claire_2026.pdf RAZ_Hilaire_Claire_2026.pdf 1 E9BF7B15C8170FC983D59D9B67A07B04 b204dadd13784bc3fee13b0929e1e4f810dbbcad450fd34bce067c354a0c4b33 2e101e11-282b-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33352 Fakulteta za matematiko, naravoslovje in informacijske tehnologije 0 0 0