The robust chromatic number of graphs

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

Publication date 3 May 2023

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 i n V

, such that

v i n f (v) i n E

(the mapping

f : V o E c u p v a r n o t h i n g

is allowed to be non-injective), and

(i i)

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'an-type problems. In this paper, we introduce a systematic investigation of the graph invariant 1-robust chromatic number, denoted as

o m e g a_{1} (G)

. This invariant is defined as the minimum chromatic number

c h i (G_{f})

among all 1-removed subgraphs

G_{f}

of

G

. We also examine other standard graph invariants in a similar manner.

This page was built for publication: The robust chromatic number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435136)