The robust chromatic number of graphs

Abstract

A 1-removed subgraph $G_f$ of a graph $G=(V,E)$ is obtained by $(i)$ selecting at most one edge $f(v)$ for each vertex $v\in V$, such that $v\in f(v)\in E$ (the mapping $f:V\to E\cup \{\varnothing \}$ 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 ${\omega }_1(G)$. This invariant is defined as the minimum chromatic number $\chi (G_f)$ among all 1-removed subgraphs $G_f$ of $G$. We also examine other standard graph invariants in a similar manner.