Article in press
Authors:
Csilla Bujtás
Department of Mathematics, University of Ljubljana,
Jadranska 19,
Ljubljana 1000, Slovenia
email: csilla.bujtas@fmf.uni-lj.si
Máté Vizer
Department of Computer Science, Budapest University of Technology and Economics
email: vizermate@gmail.com
Title:
The robust chromatic number of certain graph classes
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-05-08 , Revised: 2024-12-28 , Accepted: 2024-12-28 , Available online: 2025-01-29 , https://doi.org/10.7151/dmgt.2576
Abstract:
A 1-selection $f$ of a graph $G$ is a partial function $f: V(G)\rightarrow 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.
Keywords:
graph coloring, robust coloring
References:
- G. Bacsó, B. Patkós, Zs. Tuza and M. Vizer, The robust chromatic number of graphs, Graphs Combin. 40 (2024) 89.
https://doi.org/10.1007/s00373-024-02817-1 - P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford 12 (1961) 313–320.
https://doi.org/10.1093/qmath/12.1.313 - N.J. Fine and R. Harrop, Uniformization of linear arrays, J. Symb. Log. 22 (1957) 130–140.
https://doi.org/10.2307/2964174 - A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford 18 (1967) 369–384.
https://doi.org/10.1093/qmath/18.1.369 - B. Patkós, Zs. Tuza and M. Vizer, Extremal graph theoretic questions for q-ary vectors, Graphs Combin. 40 (2024) 57.
https://doi.org/10.1007/s00373-024-02787-4 - F. Soulignac, Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory, J. Graph Algorithms Appl. 21 (2017) 455–489.
https://doi.org/10.7155/jgaa.00425
Close