Toroidal graphs have chromatic number at most $7$

173 Views Asked by At

I'm trying to prove that if $G$ is a toroidal graphs, then $\chi(G) \leq 7$.

I embedded $K_7$ in the torus and thus there exists a toroidal graph with chromatic number at least $7$, and I showed that $K_8$ isn't toroidal. I'm trying to see if I can combine these two results somehow to prove the statement, but I'm stuck. I tried to think of all $7$ vertex subsets of $G$ as subsets of $K_7$ (and therefore have chromatic number at most $7$, or I think I could even lower this to maybe $6$ unless it is $K_7$ itself but I'm unsure) and then show that no $8$ vertex subset could have chromatic number of $8$. I then wanted to "glue" together these subsets to show that $G$ itself has chromatic number at most $7$.

However, I'm doubtful this approach will work, because it seems too naïve.