If a chart can be tinted with max $4$ shades, is it planar?

There is a theory that every planar chart can be tinted with $4$ shades as if no $2$ surrounding vertices have the very same shade. Is the contrary real too?

0
2019-05-18 21:52:42
Source Share
Answers: 1

No. Take into consideration $K_{3,3}$, the chart with 2 collections of 3 vertices each such that every vertex in one set is attached to every vertex in the various other. It is not planar yet can be tinted with simply 2 shades. Extra usually, take any kind of thick bipartite chart - it is still 2 - colorable, yet much from planar.

An image of $K_{3,3}$ (in addition to $K_5$):

0
2019-05-21 07:41:52
Source