Preskoči na glavno vsebino

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.