20.500.12556/RUL-180285 The robust chromatic number of certain graph classes A $1$-selection $f$ of a graph $G$ is a partial function $f : V (G) \to E(G)$ such that $f(v)$ is incident to $v$ for every vertex $v$, where $f$ is defined. The $1$- removed $G_f$ is the graph $(V (G), E(G) \setminus\ f[V (G)])$. The ($1$-)robust chromatic number $\chi_1(G)$ is the minimum of $\chi(G_f)$ over all $1$-selections $f$ of $G$. We determine the robust chromatic number of complete multipartite graphs and Kneser graphs and prove tight lower and upper bounds on the robust chromatic number of chordal graphs and some of their extensively studied subclasses, with respect to their ordinary chromatic number. graph coloring robust coloring barvanje grafa robustno barvanje true false true Angleški jezik Slovenski jezik Članek v reviji 2026-03-05 11:10:26 2026-03-05 11:10:28 2026-03-06 04:33:07 0000-00-00 00:00:00 2025 0 0 Str. 1139-1155 no. 4 Vol. 45 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-01-01 519.17 1234-3099 10.7151/dmgt.2576 270576899 DMGT-2576.pdf DMGT-2576.pdf 1 637602566C2A6F0C5A2DFE9884A84EB8 f3070e02eedca749bbca368f94fafafc684798fdfc7b928b19a3819085ede9a2 a9b40460-187b-11f1-a1ba-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=229492 https://www.dmgt.uz.zgora.pl/publish/article.php?doi=2576 1 2e4d9ac4-187b-11f1-a1ba-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=229486 Fakulteta za matematiko in fiziko 0 0 0