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.$

Improve this question
$\endgroup$
3
  • $\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
    Commented Aug 28, 2013 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
    Commented Aug 28, 2013 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
    Commented Aug 28, 2013 at 17:32

2 Answers 2

Reset to default
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.

Improve this answer
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

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