The robust chromatic number of certain graph classes

Bacsó, Gábor (author), Bujtás, Csilla (author), Patkós, Balázs (author), Tuza, Zsolt (author), Vizer, Máté (author)

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.

• Language: English
• Keywords: graph coloring, robust coloring
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2025
• Year: 2025
• Number of pages: Str. 1139-1155
• Numbering: Vol. 45, no. 4
• PID: 20.500.12556/RUL-180285
• UDC: 519.17
• ISSN on article: 1234-3099
• DOI: 10.7151/dmgt.2576
• COBISS.SI-ID: 270576899
• Publication date in RUL: 05.03.2026

Record is a part of a journal

• Title: Discussiones mathematicae : Graph theory
• Shortened title: Discuss. Math., Graph Theory
• Publisher: Technical University Press
• ISSN: 1234-3099
• COBISS.SI-ID: 7487065

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

• Language: Slovenian
• Keywords: barvanje grafa, robustno barvanje