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.


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$.

  • 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