The robust chromatic number of certain graph classes
For a nonnegative integer \(s\), an \(s\)-selection of a graph \(G\) is an assignment \(f\) that deletes at most \(s\) incident edges from each vertex. The \(s\)-robust chromatic number \(\chi_s(G)\) is the minimum chromatic number of the resulting graph \(G_f\). This paper focuses on the case \(s=1\). The authors determine \(\chi_1\) exactly for complete multipartite graphs and Kneser graphs. For chordal graphs and their subclasses, they establish tight bounds: for split graphs \(\chi_1(G)\le\lceil\frac{\chi(G)-1}{3}\rceil+1\), while for chordal graphs in general \(\chi_1(G)\le\lceil\chi(G)/2\rceil\), both bounds being sharp. They also prove that for unit interval graphs \(\chi_1(G)=\chi(G)/3+O(1)\). The proofs combine structural graph theory with extremal set theory, particularly in the context of Kneser graph results, where the Erdős-Ko-Rado and Hilton-Milner theorems are applied.
- Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
- Extremal graph theoretic questions for q-ary vectors
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- The robust chromatic number of graphs
- Uniformization of linear arrays
This page was built for publication: The robust chromatic number of certain graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6892106)
