Charles Explorer logo
🇬🇧

Coloring count cones of planar graphs

Publication at Faculty of Mathematics and Physics |
2022

Abstract

For a plane near-triangulation (Formula presented.) with the outer face bounded by a cycle (Formula presented.), let (Formula presented.) denote the function that to each 4-coloring (Formula presented.) of (Formula presented.) assigns the number of ways (Formula presented.) extends to a 4-coloring of (Formula presented.). The Block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function (Formula presented.) belongs to a certain cone in the space of all functions from 4-colorings of (Formula presented.) to real numbers.

We investigate the properties of this cone for (Formula presented.), formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture.