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$).

$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$).

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)$ ).


1 Answer 1


Conjecture 2 is already proved.
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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.