For a homework assignment we received the exercise.
Let $G = (V, E)$ be a graph with $V = \{1, 2, . . . , n\}$ and $\omega(G) = 2$. We construct the graph $M(G)$ by making the disjoint union of $G$ with the graph $K_1,_n$ (whose bipartition of vertices is $(\{0\}, \{1', 2', . . . , n'\})$ and by adding all the edges $\bigcup ij\in E(G)\{i'j, j'i\}$.
Prove that $ \omega (M(G)) = 2 $ and that $ \chi(M(G)) = \chi(G) + 1$.
Deduct that, $\forall p ∈ N^*$ , $\exists K_3-free$ graphs with chromatic number $p$.
I am struggling with starting the proof so please help with an idea or some pointers. Thank you.
Ideas to start...
Firstly it's not hard to show that $M(G)$ can only produce a $K_3$ if such a clique is already present in $G$. This gives your result that $\omega(M(G))=2$.
Then the chromatic number $\chi(M(G)-\{0\})$ is the same as $\chi(G)$ simply by colouring every $i'$ as $i$ (since it connects to all the neighbours of $i$), so the addition of vertex $0$ requires one extra colour, otherwise $G$ would require fewer colours.
The final point can be obtained by iteratively applying the $M$ transform.