0
$\begingroup$

A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.

A minor of graph G is a graph obtained from G by means of a sequence of vertex and edge deletions and edge contractions. A graph G is said to be minor-k-colorable if every minor of G is k-colorable. Clearly, planar graphs are minor-4-colorable.

My question: is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ I don't understand. Isn't a minor of a toroidal graph also toroidal? So how is "toroidal graphs are minor-$c$-colorable" different from "toroidal graphs are $c$-colorable"? And aren't toroidal graphs $7$-colorable? And by the way, how is it "clearly" that planar graphs are minor-$4$-colorable?? $\endgroup$
    – bof
    Commented Sep 22, 2023 at 5:03
  • $\begingroup$ Toroidal graphs (and their minors, which are also toroidal) are $7$-colorable, as was shown by Heawood in 1890. en.wikipedia.org/wiki/Heawood_conjecture $\endgroup$
    – bof
    Commented Sep 24, 2023 at 1:34

0

Reset to default

You must log in to answer this question.