show a graph is not 2-choosable

210 Views Asked by At

I want to prove that the following graph is not 2-choosable: enter image description here

If I let $\{1,2\}$ be the list at each vertex, then it is possible to colour the graph; you start with say 1, and then colour each vertex in clock-wise manner 2-1-2-1-2. So I've trying to use some variation in my lists. Say each list except for one is $\{1,2\}$, and the different list is $\{1,3\}$ or $\{2,3\}$, then wherever we place it, we are able to find a proper colouring. Now I've checked other possibilities too (though not each one), like e.g. when we have two lists that are different, and the rest is $\{1,2\}$. But now it's become senseless counting/checking. Is there a way for me to go about this smartly? There are too many possibilities to check by hand.

The only theorem that came to mind is to look for a kernel-perfect orientation such that $1+d^+(x)=2$ for each vertex, but I didn't even manage to find an orientation with that property. I tried removing the middle vertical edge and finding a kernel-perfect orientation for the remaining cycle, but that's impossible if we want $1+d^+(x)=2$ for each vertex (because there are only two orientation possible; a clockwise and an anti-clockwise one, and these are not kernel-perfect).

Apart form that, I have no idea how to proceed.

1

There are 1 best solutions below

1
On BEST ANSWER

Start by assigning the list $\{1,2\}$ to each of the two middle vertices. Then there are two ways to colour those two vertices: (I) give colour $1$ to the top middle vertex, colour $2$ to the bottom middle vertex; or (II) give colour $2$ to the top middle vertex, colour $1$ to the bottom middle vertex.

Now the plan is to make something go wrong on the left side in case (I), and to make something else go wrong on the right side in case (II).

In case (I), with the top middle vertex coloured $1$ and the bottom middle vertex coloured $2,$ we will get stuck on the left side if the upper left vertex has list $\{1,3\}$ and the lower left vertex has list $\{2,3\}.$

I leave case (II) as an exercise for the reader.