1
$\begingroup$

How do I start the proof? Do I start by creating any triangle free graph or is there a theorem that I need to use?

$\endgroup$

2 Answers 2

2
$\begingroup$

The easiest way to do this is with the probabilistic method. I'll give you a quick outline:

  1. Prove that every triangle-free graph has at most $\lfloor n^2 /4\rfloor$ edges.
  2. Randomly color each vertex of your graph, independently and uniformly with $\lfloor 2 \sqrt{n} \rfloor$ colors.
  3. Calculate the expected number of edges that are incident on vertices of the same color.
  4. Conclude that there exists a proper coloring with $\lfloor 2 \sqrt{n} \rfloor$ colors, implying that the chromatic number is $\leq 2 \sqrt{n}.$

EDIT (~4 years later): I don't think this sketch works, I honestly have no idea how I imagined it did. Here's a more legitimate one.

Let's prove it by induction:

  1. Show that since G is triangle free it has an independent set of size $\sqrt{n}$ [Hint: if there is a vertex of degree $\sqrt{n}$ its neighbors form an independent set; if all vertices have degree $< \sqrt{n}$ how big is the biggest independent set?].

  2. Color your biggest independent set. You now have a graph on $n-\sqrt{n}$ vertices that you want to color with $2\sqrt{n} - 1$ colors, which follows by induction.

$\endgroup$
4
  • $\begingroup$ I tried to follow the outline, but I got stuck between steps 3 and 4. With $2\sqrt n$ colors and $n^2/4$ edges, I get $\frac1{2\sqrt n}\cdot\frac{n^2}4$ for the expected number of edges that are incident on vertices of the same color. Is that right? How do I conclude from that that there is a proper coloring with $\lfloor2\sqrt n\rfloor$ colors? $\endgroup$
    – bof
    Jul 7, 2020 at 4:29
  • $\begingroup$ By the way, where do we use "triangle-free", besides step 1? Because of course a graph with $n$ vertices and $n^2/4$ edges can have chromatic number much bigger than $2\sqrt n$. $\endgroup$
    – bof
    Jul 7, 2020 at 4:36
  • $\begingroup$ @bof, thanks for commenting, I haven't the slightest idea what I was thinking. I think both of your criticisms are valid; I must have made some calculational mistake at the time. I replaced it with a legit proof. $\endgroup$
    – Marcus M
    Jul 7, 2020 at 5:32
  • $\begingroup$ I wasn't expecting to hear from you so soon, and I've already started composing my own proof, so I'll finish it and post it even if it's the same idea as your corrected proof. $\endgroup$
    – bof
    Jul 7, 2020 at 5:37
0
$\begingroup$

Let $G=(V,E)$ be a triangle-free graph on $n$ vertices, and let $k=\lfloor\sqrt n\rfloor$. I will show that $\chi(G)\le2k$. I assume that $n\gt8$ (and so $k\ge2)$ the smaller cases being trivial.

Let $\mathcal S=\{S_1,\dots,S_m\}$ be a maximal collection of pairwise disjoint independent sets of cardinality $k$; then $mk\le n\lt(k+1)^2$, so $m\le k+2$.

Let $S=S_1\cup\cdots\cup S_m$ and let $T=V\setminus S$, so that $\chi(G)\le\chi(G[S])+\chi(G[T])$.

Because $\mathcal S$ is maximal, $T$ contains no independent set of cardinality $k$. Since $G$ is triangle-free, this means that $G[T]$ has maximum degree less than $k$. It follows that $\chi(G)\le\chi(G[S])+\chi(G[T])\le m+k$.

Case 1. If $m\le k$ then $\chi(G)\le m+k\le2k$.

Case 2. If $m=k+1$ then $|T|=n-|S|\le(k^2+2k)-(k+1)k=k$ and $\chi(G)\le\chi(G([S])+\chi(G[T])\le(k+1)+(k-1)=2k$, unless $G([T])$ is a complete graph of order $k$. But in that case we have $k\le2$ (since $G$ is triangle-free) and $n\le8$, contrary to our assumption that $n\gt8$.

Case 3. If $m=k+2$ then $|S|=k^2+2k=n$ and $S=V$, so $\chi(G)=m=k+2\le2k$.

$\endgroup$

You must log in to answer this question.

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