Abstract:

I present three problems for which there are no known good algorithms for constructing a solution.

First is a "list colouring" extension of the Four Colour Theorem. Let $G$ be a $3$-regular graph embedded on the plane, where each edge of $G$ has been provided with a list of three "allowed" colours. Find a proper edge colouring of $G$ where each edge gets a colour from its own list.

Second is the following "faithful circuit cover" problem. Let $G$ be a graph with multiple edges allowed. Find a decomposition of the edges of $G$ into circuits of length at least three.

Third is a type of max-flow min-cut problem. Let $G$ be a graph embedded on a surface (such as the double torus). Find the shortest circuit in $G$ which is a contractible curve in the surface.

The first two problems are known to have solutions (under certain natural hypotheses), but the existence proofs are algebraic or otherwise nonconstructive. The third problem can be solved on the projective plane, torus, and Klein bottle.