The robust chromatic number of certain graph classes

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

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.

• Jezik: Angleški jezik
• Ključne besede: graph coloring, robust coloring
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.01.2025
• Leto izida: 2025
• Št. strani: Str. 1139-1155
• Številčenje: Vol. 45, no. 4
• PID: 20.500.12556/RUL-180285
• UDK: 519.17
• ISSN pri članku: 1234-3099
• DOI: 10.7151/dmgt.2576
• COBISS.SI-ID: 270576899
• Datum objave v RUL: 05.03.2026

Gradivo je del revije

• Naslov: Discussiones mathematicae : Graph theory
• Skrajšan naslov: Discuss. Math., Graph Theory
• Založnik: Technical University Press
• ISSN: 1234-3099
• COBISS.SI-ID: 7487065

Licence

• Licenca: CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
• Opis: Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: barvanje grafa, robustno barvanje