Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
For every simple planar graph G and simple cycle C in G, is there always a proper vertex-coloring of G in four colors such that the vertices in C only use three colors?
(of course, the vertex-coloring of G exists according to the four-color theorem, the questions is whether we can always satisfy the additional constraint that a given simple cycle C only uses three colors)
Found the answer myself, much simpler than I thought (once one actually starts searching for a counter-example instead of a proof of existence).
The answer is NO, and the counter example is G=K4 (complete graph on four vertices). That graph is planar and Hamiltonian, so by choosing C as a Hamiltonian cycle in K4 we need four colors for the vertices in C in any proper vertex coloring, because all four vertices need mutually different colors.
