4
$\begingroup$

Are there any concrete constructions of graphs of both high girth and chromatic number?

Of course there is the seminal paper of Erdős which proves the existence of such graphs via the probabilistic method, but this method does not give an idea at all how these graphs look like. I know there are some constructions for high odd girth and high chromatic number, e.g. multi-shift graphs and generalized Mycielskians (maybe Kneser graphs also work, but if a Kneser graph has chromatic number at least 4, it contains a $C_4$). Is there maybe an explicit construction for expander graphs which meets both of these requirements?

Maybe there is a way to relax chromatic number to make it known again if the original question is too hard:

Is there a concrete construction of graphs with high girth and high minimum degree?

The following is a construction of graphs of girth 8 and arbitrarily high minimum degree: $V=[k]^k\times \{p,g\},E=\{\{P,G\}\mid P_{k+1}=p,G_{k+1}=g,P_{[k]\setminus G_k}=G_{[k-1]} \}$, where $P_I\subset [k]^I$ denotes the subtuple when restricted to the indices in $I$.

However I have no idea how to generalize this construction. For instance is there a way to increase the girth of a graph without lowering its minimum degree/chromatic number? I think that is enough questions for now :)

Improve this question
$\endgroup$
4
  • $\begingroup$ The generalized Mycielski construction might help with Q1: en.wikipedia.org/wiki/Mycielskian#Cones_over_graphs $\endgroup$
    – ho boon suan
    Commented Jun 20, 2022 at 10:18
  • 1
    $\begingroup$ certain Ramanujan graphs have large girth and chromatic number; a constrution is described here $\endgroup$
    – Manfred Weis
    Commented Jun 20, 2022 at 16:25
  • $\begingroup$ Thanks for the quick references, the generalized Mycielskians unfortunately contain $C_4$ though if the original graph contains a vertex of degree at least 2. I'll look into the Ramanujan graph construction, it looks promising on a first look. $\endgroup$
    – Felix Schröder
    Commented Jun 21, 2022 at 12:07
  • $\begingroup$ I just found a very similar question actually on Mathematics Stack Exchange: math.stackexchange.com/questions/1489355/… $\endgroup$
    – Felix Schröder
    Commented Jun 21, 2022 at 12:08

1 Answer 1

Reset to default
3
$\begingroup$

Yes, there are many explicit constructions, although some of them are rather complicated. See this talk of Noga Alon, where he presents a very comprehensive history of the problem. Probably the simplest known explicit construction is given at the end of the talk, and is due to Alon, Kostochka, Reiniger, West, and Zhu. Their construction also works for hypergraphs. See this paper.

Improve this answer
$\endgroup$
1
  • $\begingroup$ See also my answer to a previous MO question: mathoverflow.net/a/281544/25028. As stated there, I believe the first explicit construction is due to Lovász. $\endgroup$
    – Sam Hopkins
    Commented Jul 6, 2022 at 23:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .