<p>Conjecture 2 is already proved.<br />
Quote from J.A. Tilley, The a-graph coloring problem(2017):</p>
<blockquote>
<p>Theorem A.1. Let <span class="math-container">$G$</span> be an a-graph with boundary cycle <span class="math-container">$uxvy$</span> for the exterior 4-face and let <span class="math-container">$G$</span> have a 4-coloring <span class="math-container">$c$</span>. Suppose, without loss of generality, that <span class="math-container">$c(x)=1$</span>, <span class="math-container">$c(y)=1$</span> or 2, <span class="math-container">$c(u)=3$</span>, and <span class="math-container">$c(v)=3$</span> or 4. Then there is either a 1–2 path between <span class="math-container">$x$</span> and <span class="math-container">$y$</span> or a 3–4 path between <span class="math-container">$u$</span> and <span class="math-container">$v$</span>.</p>
</blockquote>
<blockquote>
<p>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.</p>
</blockquote>
<p><em>Definiton:</em> in the above paper, an <em>a-graph</em> is a plane graph such that one face has a 4-vertex cycle as boundary and all other faces have a triangle as boundary.</p>

CC BY-SA 4.0
2020-10-15T06:35:27.443Z
2020-10-15T06:35:27.443Z
Cyriac Antony
<p>The question/task is to prove/disprove the conjecture below.</p>
<p>Let <span class="math-container">$G$</span> be a maximal planar graph with a 4-coloring <span class="math-container">$f$</span>. Let <span class="math-container">$(a,b,c,d)$</span> be a cycle in <span class="math-container">$G$</span>. Let <span class="math-container">$S$</span> be the collection of all <span class="math-container">$a,c$</span>-paths in <span class="math-container">$G$</span> and all <span class="math-container">$b,d$</span>-paths in <span class="math-container">$G$</span>.<br />
<strong>Conjecture:</strong> At least two members of <span class="math-container">$S$</span> are bicolored.<br />
(i.e., there exist distinct paths <span class="math-container">$Q_1,Q_2\in S$</span> and colors <span class="math-container">$i,j,k,l\in\{1,2,3,4\}$</span> such that <span class="math-container">$f(u)\in\{i,j\}$</span> for every vertex <span class="math-container">$u$</span> on <span class="math-container">$Q_1$</span> and <span class="math-container">$f(v)\in\{k,l\}$</span> for every vertex <span class="math-container">$v$</span> on <span class="math-container">$Q_2$</span>).</p>
<p><em>Definitions:-</em><br />
<span class="math-container">$G$</span> is a <em>maximal planar graph</em> if it can be drawn on a plane such that no edges cross and boundary of every face is a triangle. A <em>4-colouring</em> <span class="math-container">$f$</span> of <span class="math-container">$G$</span> is a function <span class="math-container">$f:V(G)\to\{1,2,3,4\}$</span> such that <span class="math-container">$f$</span> map endpoints of each edge to different 'colors' (i.e. <span class="math-container">$f(u)\neq f(v)$</span> for every edge <span class="math-container">$uv$</span> of <span class="math-container">$G$</span>).</p>
<p>Notes:-<br />
It is easy to see that the conjecture is true if the cycle <span class="math-container">$(a,b,c.d)$</span>
is tricolored (or bicolored). The following is the crux of the conjecture.</p>
<p>Let <span class="math-container">$G$</span> be a planar graph with a 4-coloring <span class="math-container">$f$</span>. Let <span class="math-container">$(a,b,c,b)$</span> be a cycle in <span class="math-container">$G$</span> such that boundary of each face inside the cycle is a triangle. Suppose that the cycle <span class="math-container">$(a,b,c,d)$</span> receives all four colors.<br />
<em>Conjecture 2:</em> Then, there is a bicolored <span class="math-container">$a,c$</span>-path or a bicolored <span class="math-container">$b,d$</span>-path inside the cycle.<br />
If Conjecture 2 is true, then the main conjecture above is true (apply Conjecture 2 to outside region of the cycle <span class="math-container">$(a,b,c,d)$</span> ).</p>

<graph-theory><planar-graphs><graph-colouring>
A conjecture on 4-coloring maximal planar graphs
Cyriac Antony
# A conjecture on 4-coloring maximal planar graphs

(Asked by: username_0 on 2020-10-14)

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

**Tags:** graph-theory, planar-graphs, graph-colouring


---

## 1 answers

### Answer by username_0 on 2020-10-15. Score: 1 | Accepted answer

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.


---

