Big mono-chromatic subgraphs of vertex 2-colourings 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.
 A: This is a funny coincidence :-)
I posted a manuscript on arXiv 2 days ago, where we show some results about the complexity of computing what you call $c(\Gamma)$.
See the final section of https://arxiv.org/abs/1402.2475
We show that it is NP-hard to approximate $c(\Gamma)$ within a constant multiplicative factor, even in very specific families of graphs, such as 2-degenerate triangle-free planar graphs, or 2-degenerate graphs of girth at least 8, or graphs with girth larger than any given constant (the girth is the length of a shortest cycle). 
Even if you are not interested by the complexity results, the proofs give you ways to construct graphs $G$ within these classes for which $c(G)$ is unbounded from above (showing that the lower bounds you are looking for are not constant for these classes).
Are you interested in a particular class of graphs, besides triangular grids?
A: See https://arxiv.org/pdf/1303.2487.pdf and the references therein. For example, it says  Haxell, Szabó and Tardos proved that every graph with maximum degree at most 5 can be 2-colored in such a way that all monochromatic components have size at most 20000. Thus your c parameter is <= 20000 for max degree 5 graphs. I am sure more is known. Follow the references in the above paper. 
