I'm not a graph theorist, but the following quantity came up in my work and I'm curious if it has been studied. Given a connected finite graph $\Gamma = (V,E)$ define: $$ c(\Gamma) = \min_{f : V \rightarrow \{0,1\}} \max_{G \subseteq \Gamma} |V(G)| $$ where the minimum runs over all vertex 2-colourings and the maximum runs over all connected mono-chromatic subgraphs $G \subseteq \Gamma$.

Are there non-trivial lower bounds for $c(\Gamma)$ for general graphs $\Gamma$?

What I'm looking for is some easier to compute quantity which will lower bound $c(\Gamma)$.

For example, if we take a cyclic graph of odd order we get $c(C_{2k+1}) = 2$. Complete graphs give us: $c(K_n) \geq n/2$. It has been pointed out to me that $c(\Gamma)$ can be thought of as measure of how far from bi-partite $\Gamma$ since we have that $c(\Gamma) = 1$ for all bi-partite $\Gamma$.

**Edit:** Consider the adjacency graph of an $n \times n$ Hex board, which write $H_n$. It's well known that when the board is full (its vertices have been 2-coloured) some player has won. This forces a path between non-adjacent edges of the grid. Thus we have $c(H_n) = n$. Note that $H_n$ has $|V| = n^2$ and maximal degree six.

Is it well understood why $H_n$ has such nice lower bounds on $c(H_n)$?

I've read Gale's famous article on Hex and Brouwer, but the larged mono-chromatic subgraph comes out like a rabbit from a hat.