Lower bound example on the Greedy coloration of a planar graph

Question

Context

A coloring of a graph $G=(V,E)$ is an assignation of a color for each vertex $c:V\rightarrow \{1,\dots, s\}$ such that two adjacent vertices have distinct colors: $uv\in E \Rightarrow c(u)\neq c(v)$.

Consider the following recursive algorithm that computes a greedy coloring of a graph $G$.

1. find a vertex $v$ with minimum degree,
2. recursively compute a coloring of $G\setminus v$,
3. complete this coloring by assigning to $v$ the smallest color available.

When the graph is planar, by a simple manipulation of the Euler Characteristic one can show that there is always a vertex $v$ of degree $d(v)\le 5$. Since the class of planar graphs is stable by vertex deletion, this algorithm produces a coloration of a planar graph with $c\le 6$ colors.

(the four color theorem tells us that any planar graph has a coloring with $4$ colors, and some planar graphs like $K_4$ need exactly four colors.)

Questions

• Is $6$ the best upper bound known for this greedy algorithm on planar graphs ?
• Is there an example of a planar graph on which the algorithm above returns a coloring with $5$ (or $6$) colors ?

Remark. Planar graphs are graphs that can be embedded on the sphere. For graphs that can be drawn on more general surfaces with Euler Characteristic $\chi$ (except for the Klein Bottle), this greedy algorithm returns a coloring with $\gamma(\chi)$ colors where $\gamma(\chi)$ is the size of the maximum clique that can be embedded on a surface of characteristic $\chi$, thus suggesting that the greedy coloring is somehow optimal for higher genus graphs (see Heawood Conjecture).

Answer 1

This algorithm is known as "smallest-last coloring"; see, for example, Matula and Beck, Smallest-Last Ordering and Clustering and Graph Coloring Algorithms.

It is not always optimal for planar graphs. The first "slighty-hard" case is the triangular prism, which is 3-colorable, but for which some choices of minimum-degree vertex lead to a 4-coloring. The first hard example is the antiprism graph shown below: it can be verified that although its chromatic number is 4, any way of executing the smallest-last coloring algorithm leads to a 5-coloring. (Kosowski and Manuszewski, Classical coloring of graphs)

I don't know if there are any cases where the smallest-last coloring algorithm will always use 6 colors on a planar graph. I haven't even found any "slightly-hard" cases of this type, though everyone seems to assume that they exist.

However, there are examples where this algorithm will (given unfortunate choices of minimum degree vertex, not for all possible choices) use arbitrarily many colors on a non-planar but bipartite graph (which is 2-colorable). Coleman and Moré, Estimation of sparse Jacobian matrices and coloring problems give the example of a graph on vertex set $\{u_i, v_i, p_i, q_i, r_i, s_i : 1 \le i \le n\}$, with the following edges:

• A complete bipartite graph between $\{p_1, \dots, p_n\}$ and $\{r_1, \dots, r_n\}$;
• A complete bipartite graph between $\{q_1, \dots, q_n\}$ and $\{s_1, \dots, s_n\}$;
• A complete bipartite graph between $\{u_1, \dots, u_n\}$ and $\{v_1, \dots, v_n\}$, with the perfect matching $\{u_1v_1, \dots, u_nv_n\}$ deleted;
• Edges $u_i p_j$ and $v_i q_j$ for all $1 \le i \le j \le n$.

This is shown below for $n=4$:

The bad coloring uses $n+1$ colors and is obtained when coloring vertices in the order $$q_1, s_1, \dots, q_n, s_n,\;p_1, r_1, \dots, p_n, r_n,\;u_1, v_1, \dots, u_n, v_n$$ (that is, deleting vertices in the reverse of that order).