Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Mr. Paint and Mrs. Correct. | Mr. Paint and Mrs. Correct Uwe Schauz Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals Dhahran 31261 Saudi Arabia schauz@ Submitted Jul 21 2008 Accepted Jun 19 2009 Published Jun 25 2009 Mathematics Subject Classifications 91A43 05C15 05C20 05C10 Abstract We introduce a coloring game on graphs in which each vertex v of a graph G owns a stack of G 1 erasers. In each round of this game the first player Mr. Paint takes an unused color and colors some of the uncolored vertices. He might color adjacent vertices with this color - something which is considered incorrect . However Mrs. Correct is positioned next to him and corrects his incorrect coloring . she uses up some of the erasers - while stocks stacks last - to partially undo his assignment of the new color. If she has a winning strategy . she is able to enforce a correct and complete final graph coloring then we say that G is Gpaintable. Our game provides an adequate game-theoretic approach to list coloring problems. The new concept is actually more general than the common setting with lists of available colors. It could have applications in time scheduling when the available time slots are not known in advance. We give an example that shows that the two notions are not equivalent i-paintability is stronger than Glist colorability. Nevertheless many deep theorems about list colorability remain true in the context of paintability. We demonstrate this fact by proving strengthened versions of classical list coloring theorems. Among the obtained extensions are paintability versions of Thomassen s Galvin s and Shannon s Theorems. Introduction There are many papers about graph coloring games. Originally these games were introduced with the aim to provide a game-theoretic approach to coloring problems. The hope was to obtain good bounds for the chromatic number of graphs in particular with regards to the Four Color Problem see . BGKZ and the literature cited .
