3
$\begingroup$

The classic join of two graphs $G$ and $H$ results in $G \vee H$ whose chromatic number

$\chi(G \vee H)$ = $\chi(G)$ + $\chi(H)$.

$G \vee H$ = $G \cup H \cup$ Complete bipartite between vertices of $G$ and $H$.

This introduces $n_G.n_H$ new edges. I am looking for other operations which increases the chromatic number with a limited increase in the number of edges. The Mycielskian is one of them. Are there any other such simple tricks for increasing the chromatic number? I am looking for a construction where fewer triangles(new) would be formed. Any references on such works are welcomed.

Thank you for going through this.

$\endgroup$
1
$\begingroup$

Maybe this is too obvious, but if you pick any subgraph with $\chi(G)+1$ vertices and then add edges to make it complete, the new graph has a strictly larger chromatic number and the same number of vertices and no more than $\binom{\chi(G)+1}{2}$ edges more than $G$.

$\endgroup$
  • 1
    $\begingroup$ I am really sorry for not mentioning this. Of course what you said is correct. I am looking for a construction which wouldn't allow many new triangles to be formed, as triangles limit the structure of the graph. Anyhow thanks. $\endgroup$ – user67773 Aug 13 '13 at 9:44

Your Answer

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