On Chromatic Core Subgraph of Simple Graphs

Abstract

If distinct colours represent distinct technology types that are placed at the vertices of a simple graph in accordance to a minimum proper colouring, a disaster recovery strategy could rely on an answer to the question: "What is the maximum destruction, if any, the graph (a network) can undergo while ensuring that at least one of each technology type remain, in accordance to a minimum proper colouring of the remaining induced subgraph." In this paper, we introduce the notion of a chromatic core subgraph $H$ of a given simple graph $G$ in answer to the stated problem. Since for any subgraph $H$ of $G$ it holds that $\chi (H)\le \chi (G)$, the problem is well defined.

8 Pages, 2 Figures