Hi!
I am currently reading some paper which states that 2-List Coloring problem (i.e the list of colours for every vertex is of size at most 2) is polynomial time solvable for planar graphs. The paper provides some references for the proof but they are nowhere to be found on the internet. I have tried a lot to come up with a proof myself but haven't been successful. I am hoping someone here can share a proof for it.
Also, I read somewhere that not only for planar graphs, it is polynomial time even for general graphs.
Thanks!
I don't understand your point but I think 2-list-coloring in general graph is an easy 2-SAT problem.
Let P(i) -> (vertex i chose first color). For all edge e = {u, v}, if vertex u's first color and v's first color coincide, add clause (!P(u) || !P(v)). For first / second, second / first, second / second you can do the same thing. So we can do a reduction into 2-SAT
This is helpful, thanks! :)