Problem statement:
Let $k$ be the maximum value of $\chi(G)$ on all $30$ nodes graphs with a girth of at least $6$. Find two numbers $a$ and $b$ such that $a \leq \chi(G) \leq b$ and $b – a \leq 1$.
Using the fact that for all simple graphs $G$, $\chi(G) \leq \Delta(G) + 1$, I proved that $k \leq 9$. It is also obvious that $k \geq 3$.
How did I prove that $k \leq 9$? Let's say a graph $G$ exist with $30$ nodes, girth of at least $6$ and $\chi(G) = 10$. We will find a contradiction. We know that $\chi(G) \leq \Delta(G) + 1$ so $G$ needs have a node $v$ with at least $9$ neighbors. since the girth of $G$ is at least 6, none of the neighbors of $v$ are connected to each other. we will color $v$ with $1$ and it's neighbors with $2$ ($1$ and $2$ are color indexes). now if we remove $v$ and it's neighbors and call the remaining graph $H$, we know that $\chi(H) \geq 8$, $n(H) \leq 20$. now we do the exact same thing we did with $G$, with $H$. we keep doing this until there is one or two nodes left. If you keep track of the number of colors used you will see that when we arrive at this situation we have used $8$ colors. If there is one node left or the nodes left aren't connected then we get contradiction that $\chi(G) \leq 9$, if not these two need be connected to the first node we removed because if they're not then we can color one with $1$ and get the last contradiction. but if these nodes are connected to each other and the first node we remove then they form triangle which is again a contradiction.
But now I have not made any progress for a day, I would be thankful if you could give a solution or a hint (mostly for how can I find useful a lower bound for $k$).
Best Answer
I found no graphs with $30$ nodes, girth at least $6$, and chromatic number at least $4$ at the House of Graphs. This strongly suggests that $k=3$.
The proof of the bound $k\le 4$ is rather easy. We begin from the following lemma.
Lemma. Any graph with at most $13$ nodes and girth at least $6$ has chromatic number at most $3$.
Proof. Suppose for a contradiction that there are graphs with at most $13$ nodes, girth at least $6$, and chromatic number at least $4$. Let $G$ be such graph with the minimum number of nodes. Then no node of $G$ has degree at most $2$, because otherwise we can remove this node, color the remaining nodes into three colors, and then color the node into the color distinct of the colors of its neighbors.
Pick a node $v$ of $G$ of maximum degree. Let $N$ be the set of neighbors of $v$ and $N_2$ be the set of neighbors of nodes from $N$. Since the girth of $G$ is at least $6$, the sets $N$ and $N_2$ are disjoint, distinct nodes from $N$ have no common neighbor but $v$, and no nodes from $N_2$ are adjacent. If degree of $v$ is at least $4$ then $$|\{v\}\cup N\cup N_2|=|\{v\}|+|N_1|+|N_2|\ge 1+\deg v +2\deg v\ge 13,$$ but $G$ has also nodes beyond the set $\{v\}\cup N\cup N_2$ which are adjacent with the nodes from $N_2$.
So the degree of each node of $G$ is $3$, that is the graph $G$ is cubic. But then girth of $G$ is less than $6$ (see, for instance, here), a contradiction. $\square$
Proposition. Any graph with at most $30$ nodes and girth at least $6$ has chromatic number at most $4$.
Proof. Suppose for a contradiction that there are graphs with at most $30$ nodes, girth at least $6$, and chromatic number at least $5$. Let $G$ be such graph with the minimum number of nodes. Similarly to the proof of Lemma we can suppose that the minimum node degree of $G$ is at least $4$. Let $V$ be the set of nodes of $G$. Pick any node $v\in V$. Let $N$ be the set of neighbors of $v$ and $N_2$ be the set of neighbors of nodes from $N$. Since the girth of $G$ is at least $6$, the sets $N$ and $N_2$ are disjoint, distinct nodes from $N$ have no common neighbor but $v$, and no nodes from $N_2$ are adjacent. Put $V’=\{v\}\cup N\cup N_2$. Then $|V’|=|\{v\}|+|N_1|+|N_2|\ge 1+4+3\cdot 4=17.$ By Lemma, we can properly color the subgraph of $G$ induced by $V\setminus V’$, into at most three colors. To compete the proper coloring of $G$, color the node $v$ and all nodes from $N_2$ into the additional color and all nodes from $N$ in any color distinct from it. $\square$