I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path between a specified pair of nonadjacent vertices, the chromatic number may be greater than if the constraint were not imposed. I have in mind a particular constraint of that type described in the following.
In the article http://arxiv.org/abs/1511.06872, I provide strong support for the conjecture presented below. The conjecture is interesting because if true then the 4-color theorem is obviously true. But it is also interesting for another reason just as significant. If it is true, then one can prove the 4-color theorem by means of Kempe exchanges alone for all internally 6-connected planar triangulations other than the icosahedron. The reason for the failure of Kempe exchanges in the case of the icosahedron lies with the coloring property that I described in my previously posted question. The article referenced above discusses this topic by means of equivalence classes under Kempe exchanges.
Definition. An "a-graph" is an almost-triangulated-graph; its sole non-triangular face has size 4.
Definition. Let $G$ be an a-graph with boundary cycle $uxvy$. The "chromatic number $\chi_{G}(u,v;x,y)$" is the minimum number of colors required to properly color $G$, subject to the constraint that there is a 2-color path between $x$ and $y$ that does not use the color(s) of $u$ and $v$.
Conjecture. Let $uv$ be any edge in an internally 6-connected planar triangulation $T$ and let $G$ be the a-graph obtained by deleting $uv$ to form a 4-face with boundary cycle $uxvy$. Then $max[\chi_{G}(u,v;x,y),\chi_{G}(x,y;u,v)] > 4$ if and only if $T$ is isomorphic to the icosahedron.
