3
$\begingroup$

Let $G$ be a finite graph and $X$ be a set of $\chi(G)$ colors.

Consider the following algorithm:

  • In the $i-$th step, we color the $i-$th vertex of $G$ with a random color of $X$ different of the colors of it's neighbors.

If any of the steps cannot be performed, the algorithm fails. If all vertices can be colored, the algorithm succeeds

Is it possible to order the vertices of $G$ in such a way that this algorithm always succeeds? What if $X$ has $\chi(G)+1$ colors?

This post is an attempt to generalize this problem.

$\endgroup$
5
  • $\begingroup$ Sure, it works if $G = K_n$. $\endgroup$ Commented Oct 23, 2020 at 5:51
  • $\begingroup$ I'm asking if it works for a generic graph. $\endgroup$ Commented Oct 23, 2020 at 11:54
  • $\begingroup$ By random you really mean adversarially chosen, since the only way the algorithm could be guaranteed to succeed against a random sequence is if it succeeds against every possible sequence. $\endgroup$ Commented Oct 23, 2020 at 14:54
  • $\begingroup$ @Arjuna196: you might want to look into "online graph colouring" problems. The idea is that the graph is given to you gradually, rather than all at once. I don't know much but I know that the bounds are much worse than the normal case. So it seems you can trick the algorithm so that it has to use many more colours. $\endgroup$ Commented Oct 26, 2020 at 1:32
  • 1
    $\begingroup$ @JordanMitchellBarrett This is not the same as an online graph coloring problem. In the online problem, we are looking at the worst-case order of vertices. Here, the order is best-case and just the colors chosen at every step are worst-case. $\endgroup$ Commented Oct 26, 2020 at 19:31

1 Answer 1

4
+50
$\begingroup$

The triangular prism graph is a counterexample.

By Brooks' theorem, the triangular prism graph $G$ has $\chi(G)=3$. However, no matter which vertex $v$ is left for last in the ordering, there is a proper coloring of $G-v$ that gives $v$'s three neighbors different colors, leaving no color for $v$. (And no matter how the vertices before $v$ are ordered, that proper coloring of $G-v$ is one of the possible outcomes of coloring them.)

Since $G$ is vertex-transitive, it's enough to demonstrate this for one choice of $v$, which I've done below:

enter image description here


For a counterexample if $\chi(G)+1$ colors are available, consider the circulant graph below, with $9$ vertices arranged in a circle, and edges between vertices $1$ or $2$ steps apart.

This has chromatic number $3$ (by a mod $3$ coloring around the circle). However, if $4$ colors are available, then it's possible to color the first $8$ vertices (no matter which $8$ vertices they are) so that all $4$ colors are used on the neighbors of the last vertex.

Again, since the graph is vertex-transitive, it's enough to demonstrate this for one choice of last vertex, which I've done below:

enter image description here


One final note: this problem is not really equivalent to the $2$-player game in the linked question about planar graphs.

In the $2$-player game, the sequence is not specified in advance: player A can look at the first few colors chosen by player B, and then decide which vertex to ask player B to color next. This makes the game easier for player A (and harder for player B).

If the sequence had to be specified in advance, player A would lose on some planar graphs, even with $5$ colors available. For example, here is a proof in the same style as above for the icosahedral graph:

enter image description here

However, all planar graphs have a sequence which guarantees a $6$-coloring, by putting the vertices in an order such that each vertex has at most $5$ predecessors.

$\endgroup$
2
  • $\begingroup$ Interestingly though, for the 1st example if you only pick the vertex after seeing what color has been used for the previous vertex you can win easily. This is the order, top outer vertex, left outer vertex, right outer vertex, top inner vertex. Then depedning on what number is chosen for the fourth vertex, one of the remaining two vertexes will be adjacent to the different numbers, pick that on first. $\endgroup$ Commented Jun 25, 2023 at 16:04
  • $\begingroup$ Amusingly, for the second graph, the algorithm will always succeed given 3 colours. Just pick them in clockwise order. After the first two vertices are coloured, every colouring afterwards will be forced, as each newly picked vertex will be adjacent to two previously coloured vertices with different colours themselves. $\endgroup$ Commented Jun 25, 2023 at 16:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .