The Robust Chromatic Number of Graphs

期刊论文
出版模式：

开放获取
发表日期：

2024年7月27日

查看全文

Gábor Bacsó,
Balázs Patkós,
Zsolt Tuza,
Máté Vizer

摘要

A 1-removed subgraph $G_f$ $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\in V$ $v \in V$ , such that $v\in f(v)\in E$ $v \in f (v) \in E$ (the mapping $f:V\rightarrow E \cup \{\varnothing \}$ $f : V \to E \cup {\emptyset}$ 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 $\chi _1(G)$ $χ_{1} (G)$ . This invariant is defined as the minimum chromatic number $\chi (G_f)$ $χ (G_{f})$ among all 1-removed subgraphs $G_f$ $G_{f}$ of G. We also examine other standard graph invariants in a similar manner.