Let me just expand on Josh Zelinsky’s point here and point out that in fact much more is true. We can define the *girth* of a graph to be the size of the smallest cycle (if there are no cycles, the girth is ∞.)

Obviously, a graph with girth ∞ is necessarily 2-colorable. But for finite girth, for graphs that do indeed contain a cycle, Erdos showed that you can find graphs with arbitrarily high girth and arbitrarily high chromatic number.

…except that actually, that’s only true if when we say “arbitrarily high chromatic number”, we’re only talking about *finite* possibilities for the chromatic number! I was implicitly restricting to finite graphs above. But if we want to allow infinite graphs, and if we thus similarly allow the chromatic number to be infinite, this is no longer true: It’s a theorem of Erdos and Hajnal that any graph with no 4-cycles is countably colorable!

(OK, the theorem is actually much stronger than that — what it actually says is, if a graph is not countably colorable, then it contains, for every n, a copy of the complete bipartite graph K_{n,aleph_1}. But in particular that means it contains a 4-cycle. ðŸ™‚ )

However, with a modification, the theorem becomes true for infinite chromatic numbers as well. We can define the *odd girth* of a graph to be the size of the smallest *odd* cycle (so the odd girth is ∞ if and only if the graph is 2-colorable). Restricting ourselves once again to graphs of finite odd girth, graphs that do indeed contain an odd cycle, it is indeed the case (and yes this is Erdos again ðŸ˜› ) that you can find graphs of arbitrarily high odd girth and arbitrarily high chromatic number — even if the chromatic number is allowed to be an infinite cardinal.

In particular, there are triangle-free graphs with arbitrarily high chromatic number, even if the chromatic number is allowed to be an infinite cardinal. ðŸ™‚

(The construction for this last theorem isn’t too bad, either! IIRC it goes as follows: Say you want a graph with chromatic number at least X and odd girth at least 1+2n. Take Y=℘^n(X) (i.e., take the power set of X, iterated n times), and put a total order on it (obviously using choice there, but interestingly not its full strength; it doesn’t need to be a well-order). Turn Y into a directed graph by drawing an edge from a to b if a<b. Now, given a directed graph G, we’ll define its directed line graph, L(G), to be the graph whose vertices are the edges of G, and for edges e and e’ of G, we’ll draw an edge from e to e’ in L(G) if the head of e equals the tail of e’. We’ll take L^n(G). Then the underlying undirected graph of this has the required chromatic number and odd girth!)

]]>Ah yes, so that makes the rational case of the plane not interesting.

]]>That’s not in general enough. One can have graphs without triangles with high chromatic number. The easiest example is the GrÃ¶tzsch graph which is triangle free and has chromatic number 4. https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph

]]>https://screencast.com/t/oTjOvOZy

Or is someone trying to send us a hidden message? ðŸ˜‰

]]>I know you meant that comment to be half-joking, but my initial reaction was to whether Israelis are, in fact, over-represented in TCS in comparison to other branches of math or computer science.

If in fact this is true, I would have speculated that this may have been due to large numbers of Israelis being descended from Ashkenazi Jews from Russia (including very recent emigres from Russia or elsewhere in the former Soviet Union), and thus perhaps inheriting the academic mathematical traditions that produced the likes of Andrey Kolmogorov, a pioneer in the field of TCS among many other fields.

]]>