Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "On the Oriented Game Chromatic Number"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On the Oriented Game Chromatic Number. | On the Oriented Game Chromatic Number J. Nesetrilt Dept. of Appl. Math. and Institute of Theoretical Computer Sciences ITI Charles University Prague Czech Republic nesetril@kam-enterprise.ms.mff.cuni.cz E. Sopena LaBRI Universite Bordeaux 1 345 cours de la Liberation 33405 Talence Cedex France sopena@labri.u-bordeaux.fr Submitted March 6 2000 Accepted May 18 2000. Subject Classification 05C15 68R05. Keywords oriented graph coloring coloring games. Abstract We consider the oriented version of a coloring game introduced by Bodlaender On the complexity of some coloring games Internal. J. Found. Comput. Sci. 2 1991 133-147 . We prove that every oriented path has oriented game chromatic number at most 7 and this bound is tight that every oriented tree has oriented game chromatic number at most 19 and that there exists a constant t such that every oriented outerplanar graph has oriented game chromatic number at most t. 1 Introduction Let G be an undirected graph with vertex set V G and edge set E G and X be a set of colors. We consider the two-players game defined as follows. The two players are Alice and Bob and they play alternatively with Alice having the first move. Alice s goal is to provide a proper -coloring of G and Bob s goal is to prevent her from doing so. A move consists in choosing an uncolored vertex u and assigning it a color from the set X distinct from the colors previously assigned by either player to the neighbors of u. If after V G moves the graph is colored then Alice wins otherwise Bob wins. In other This work has been partially supported by the Barrande Grant 02887-WD and the NATO Collaborative Research Grant 97-1519. IPartially supported by the Project LN00A056 of the Czech Ministry of Education. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 no. 2 2001 R14 1 words Bob wins whenever an impass is reached before the whole graph is colored that is if at some intermediate step for every uncolored vertex u and every color a u has some neighbour with color .