6
$\begingroup$

The well known result of Erdős, states that

Given integers $g > 2$ and $k > 1$ there exist a graph $G$ with $\chi(G) \geq k$ and girth at least $g.$

What I am wondering is

When can we expect equality to hold? I.e for which parameters $(g,k)$ do we have graphs with girth $g$ and chromatic number $k$?

Of course we cannot have $k=2$ and $g$ odd, but are there any other more interesting pairs $(g,k)$ for which there does not exist a graph of girth $g$ and chromatic number number $k$? In particular

Has anyone thought of searching/classifying these graphs in an analogous way as cages for girth and degree?

After what Jacob said I propose the following

What is the smallest graph of girth $4$ and chromatic number $5.$

$\endgroup$
  • $\begingroup$ Using your notation, there are easy examples for (3,k) and (k,3) for k at least 3. It might be instructive to establish an example for (k,k) as well. $\endgroup$ – The Masked Avenger Aug 28 '13 at 14:00
  • $\begingroup$ Also, one can add smaller cycles to a k colored graph. So it is a matter of k coloring arbitrarily large girth graphs. $\endgroup$ – The Masked Avenger Aug 28 '13 at 15:11
  • $\begingroup$ I think the question you want to ask is what are (bounds on) the functions v(g,k) and e(g,k), which count the smallest number of vertices respectively edges possible for a graph of girth g and chromatic number k. $\endgroup$ – The Masked Avenger Aug 28 '13 at 17:32
10
$\begingroup$

There are no more pairs (g,k). Indeed, one can start with a graph of large chromatic number and large girth. Deleting vertices one at a time, one gets a subgraph with chromatic number exactly k and girth at least g. As long as k>2, adding a disjoint cycle of length g keeps the chromatic number k and the girth will be g. For k=2 and g even, we can just take our graph to be a cycle of length g.

$\endgroup$
3
$\begingroup$

The answer to your "new" question is known: the smallest order of a 5-chromatic graph of girth 4 has 22 vertices, and there are 80 such graphs.

Tommy Jensen and Gordon F. Royle, Small graphs with chromatic number 5: A computer search, Journal of Graph Theory 19(1):107-116, 1995. link

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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