Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

kazuma_desu's blog

2-List Coloring for Planar Graphs
By kazuma_desu, history, 7 years ago, In English

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!

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply