# A conjecture on 4-coloring maximal planar graphs

The question/task is to prove/disprove the conjecture below.

Let $$G$$ be a maximal planar graph with a 4-coloring $$f$$. Let $$(a,b,c,d)$$ be a cycle in $$G$$. Let $$S$$ be the collection of all $$a,c$$-paths in $$G$$ and all $$b,d$$-paths in $$G$$.
Conjecture: At least two members of $$S$$ are bicolored.
(i.e., there exist distinct paths $$Q_1,Q_2\in S$$ and colors $$i,j,k,l\in\{1,2,3,4\}$$ such that $$f(u)\in\{i,j\}$$ for every vertex $$u$$ on $$Q_1$$ and $$f(v)\in\{k,l\}$$ for every vertex $$v$$ on $$Q_2$$).

Definitions:-
$$G$$ is a maximal planar graph if it can be drawn on a plane such that no edges cross and boundary of every face is a triangle. A 4-colouring $$f$$ of $$G$$ is a function $$f:V(G)\to\{1,2,3,4\}$$ such that $$f$$ map endpoints of each edge to different 'colors' (i.e. $$f(u)\neq f(v)$$ for every edge $$uv$$ of $$G$$).

Notes:-
It is easy to see that the conjecture is true if the cycle $$(a,b,c.d)$$ is tricolored (or bicolored). The following is the crux of the conjecture.

Let $$G$$ be a planar graph with a 4-coloring $$f$$. Let $$(a,b,c,b)$$ be a cycle in $$G$$ such that boundary of each face inside the cycle is a triangle. Suppose that the cycle $$(a,b,c,d)$$ receives all four colors.
Conjecture 2: Then, there is a bicolored $$a,c$$-path or a bicolored $$b,d$$-path inside the cycle.
If Conjecture 2 is true, then the main conjecture above is true (apply Conjecture 2 to outside region of the cycle $$(a,b,c,d)$$ ).

Quote from J.A. Tilley, The a-graph coloring problem(2017):

Theorem A.1. Let $$G$$ be an a-graph with boundary cycle $$uxvy$$ for the exterior 4-face and let $$G$$ have a 4-coloring $$c$$. Suppose, without loss of generality, that $$c(x)=1$$, $$c(y)=1$$ or 2, $$c(u)=3$$, and $$c(v)=3$$ or 4. Then there is either a 1–2 path between $$x$$ and $$y$$ or a 3–4 path between $$u$$ and $$v$$.

Proof. Suppose that G with 4-coloring c is a minimal counterexample to the theorem. Clearly G cannot have either an interior xy edge or an interior u v edge. Let X be the set of vertices of G adjacent to x; they form an internal path between u and v that includes at least one interior vertex of G. At least one of those interior vertices of G belonging to X is colored 2, for otherwise the path between u and v would be colored 3–4, contradicting the supposition. Contract the various edges joining x to each vertex of X colored 2, and change the color of x to 2. The result is a 4-colored a-graph F . The edge contractions do not create any 3–4 path between u and v . By the minimality assumption, F must therefore have a 1–2 path between x and y. Reverse the contractions and restore the color of x to 1 to reveal a 1–2 path between x and y in G, contradicting the supposition and establishing the truth of the theorem.

Definiton: in the above paper, an a-graph is a plane graph such that one face has a 4-vertex cycle as boundary and all other faces have a triangle as boundary.