0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.