Clarification on notation

50 Views Asked by At

For a graph $G$, put $δ(G) = \text{min}\{\deg_{G} (v) : v \in V\}$ (the minimum degree of $G$). Prove $χ(G) \leq 1 + \text{max}\{δ(G ) : G' \subseteq G\}$, where $G' \subseteq G$ means that $G$ is a subgraph of $G$

Does this mean that the chromatic number is the maximum of all of the minimum degrees of all of the possible subgraphs of G?

Please no hints on the solution :)

1

There are 1 best solutions below

4
On BEST ANSWER

You're right. This means that the chromatic number is less than or equal to the maximum of all the minimum degrees of all possible subgraphs of $G$ $+1$.

I think however that you meant to put $\delta(G')$ instead of $\delta(G)$ in the expression for the chromatic number.