Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Bacsó et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: