0
$\begingroup$

Prove or disprove: if $G$ is a graph such that $\chi(G) \leq \chi(S_k)$ then $G$ is embedded in $S_k$

I know that if $G$ is embedded in $S_k$ then $\chi(S_k)= max\{\chi(G)\}$ which implies $\chi(G) \leq \chi(S_k)$. But I'm not so sure about the converse.

I can see if a graph is embedded on a sphere or a torus, but for this we don't know $k$. I wonder if anyone would please show me how do I show a graph is embedded on a surface without a picture?

$\endgroup$

1 Answer 1

0
$\begingroup$

I guess this is not true, because let $G$ be a Petersen graph then $\chi(G)=3\leq 4= \chi(S_0)$ but Petersen graph is not embedded on a sphere.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .