Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
This might be trivial, but you have $c(\Gamma) \ge \frac{\chi(\Gamma)}{2}$ –  hbm Feb 12 at 4:00

2 Answers 2

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 http://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?

share|improve this answer

See http://arxiv.org/pdf/1303.2487.pdf and the references therein. For example, it says Haxell, Szabo 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.

share|improve this answer
Thanks for the reference to the Esperet and Joret, their reference to Haxell and Szabo is great. Everything they're doing is about upper bounds, which is useful, but I'm looking for lower bounds. They also make a reference to the ``famous HEX lemma'' which I had in mind while asking the question. I'll write it in to the body of the question. –  pgadey Feb 12 at 16:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.