The Robust Chromatic Number of Graphs

Abstract A 1-removed subgraph Gf G f of a graph G= (V, E) G = (V, E) is obtained by (i) selecting at most one edge f (v) for each vertex v V v ∈ V, such that v f (v) E v ∈ f (v) ∈ E (the mapping f: V E \ \ f: V → E ∪ ∅ is allowed to be non-injective), and (ii) deleting all the selected edges f (v) from the edge set E of G. Proper vertex colorings of 1-removed subgraphs proved to be a useful tool for earlier research on some Turán-type problems. In this paper, we introduce a systematic investigation of the graph invariant 1-robust chromatic number, denoted as ₁ (G) χ 1 (G). This invariant is defined as the minimum chromatic number (Gf) χ (G f) among all 1-removed subgraphs Gf G f of G. We also examine other standard graph invariants in a similar manner.