tailieunhanh - Báo cáo toán học: "Game chromatic number of Cartesian product graphs"

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: Game chromatic number of Cartesian product graphs. | Game chromatic number of Cartesian product graphs T. Bartnickiy B. Bresarz Faculty of Mathematics Computer Science and Econometrics University of Zielona Gora 65-516 Zielona Gora Poland J. Grytczuk Theoretical Computer Science Department Faculty of Mathematics and Computer Science Jagiellonian University 30-387 Kraków Poland Grytczuk@ Z. Miechowicz Faculty of Mathematics Computer Science and Econometrics University of Zielona Goóra 65-516 Zielona Góra Poland barta@ University of Maribor FEECS Smetanova 17 2000 Maribor Slovenia M. Kovse Faculty of Natural Sciences and Mathematics University of Maribor Koroska cesta 160 2000 Maribor Slovenia I. Peterinz University of Maribor FEECS Smetanova 17 2000 Maribor Slovenia Submitted Apr 9 2007 Accepted May 5 2008 Published May 12 2008 Mathematics Subject Classification 05C15 91A46 Abstract The game chromatic number Xg is considered for the Cartesian product G H of two graphs G and H. Exact values of Xg K22H are determined when H is a path a cycle or a complete graph. By using a newly introduced game of combinations we show that the game chromatic number is not bounded in the class of Cartesian products of two complete bipartite graphs. This result implies that the game chromatic number Xg G2H is not bounded from above by a function of game chromatic numbers of graphs G and H. An analogous result is derived for the game coloring number of the Cartesian product of graphs. The paper was started during a meeting in Zielona Góra. y Research supported by a PhD grant from Polish Ministry of Science and Higher Education N201 2128 33. zSupported by the Ministry of Higher Education Science and Technology of Slovenia under the grant P1-0297. The author is also with the Institute of Mathematics Physics and Mechanics Jadranska 19 1000 Ljubljana. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R72 1 1 .