$2$-coloring of $K_{1,2,2,2,2}$ without monochromatic triangles

Question

According to Turan's Theorem, $K_{1,2,2,2,2}$ is the graph of order $9$ with the maximum number of edges ($32$) that is $K_6$-free.

Any (simple) graph $G$ of order $9$ with $33$ edges or more will have $K_6$ as subgraph. This guaranties that if we color each of the edges of $G$ with either red or blue, we will obtain a monochromatic triangle in the $K_6$ subgraph (using Ramsey's number $R(3,3)=6$).

Based on this reasoning, it comes natural to ask if it is possible to color the edges of $K_{1,2,2,2,2}$ (using red or blue) such that no monochromatic triangle is formed.

I had several attempts (trying to replicate the $2$-coloring of $K_5$ that avoids monochromatic triangles), but with no luck.

Answer 1

In general, if there is a graph homomorphism $f:G\to H,$ and if the edges of $H$ can be $2$-colored without monochromatic triangles, then the same goes for $G.$ Namely, we can give each edge of $G$ the same color as its image; then the image of a monochromatic triangle in $G$ would be a monochromatic triangle in $H.$

We know that the edges of $K_5$ can be $2$-colored without monochromatic triangles. It follows that, if there is a homomorphism $f:G\to K_5,$ or in other words if $G$ is $5$-colorable, then the edges of $G$ can be $2$-colored without monochromatic triangles.

In particular, the edges of your graph $K_{1,2,2,2,2}$ can be $2$-colored without monochromatic triangles.

(By the way, there are $K_6$-free graphs, even $K_4$-free graphs, whose edges cannot be $2$-colored without forming a monochromatic triangle.)

Answer 2

The colouring of $K_5$ with two colours that avoids monochromatic triangles can be extended to $K_{2,2,2,2,1}$