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

• The algorithm is often under-specified: there are multiple choices of minimum-degree vertex. It is not hard to find examples of graphs where some of these arbitrary decisions lead to a sub-optimal coloring, but I haven't yet found an example where every way of taking the minimum-degree vertex always leads to a sub-optimal coloring. Jun 18, 2020 at 22:15
• what do you mean exactly by "sub-optimal" ? Jun 19, 2020 at 10:41
• By sub-optimal I mean worse than the chromatic number. For instance, there are planar graphs with chromatic number 4 where some (but not all) ways to do the greedy coloring end up using 5 colors instead. Jun 19, 2020 at 13:15
• Nice, can you show me this example or tell me where I can find it ? Jun 19, 2020 at 14:43

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