Gašper Fijavž: 5th color is only needed once
Datum objave: 8. 3. 2011
Seminar za teorijo grafov in algoritme
Četrtek 10. 3. 2011 ob 12:15 v predavalnici 3.05 na Jadranski 21
We show that -every- 3-connected planar graph G admits a proper 5-coloring c of vertices so that (i) no automorphism (except the identity map) preserves both G and c (ii) there exists a single vertex which is colored with color 5. We have used the word -every- in a liberal manner: there are two exceptional graphs which fail the above property.