乘积图的博弈染色数
The Game Coloring Number of Product Graph
摘要: 本文讨论的图是两棵树的乘积图. 分别研究了树和树的笛卡尔积图、直积图和强积图的 (a, 1)-博弈染色数, 给出了三种乘积图的 (a, 1)-博弈染色的上界. 特殊地, 如果其中一棵树是一条路, 那么我们类似的可以得出关于树和路的乘积图的 (a, 1)-博弈染色数的结果.
Abstract: The graph discussed in this article is a product graph of two trees. We study the (a, 1)-game coloring numbers of the Cartesian product graph, direct product graph and strong product graphs of two trees, and give the upper bounds of (a, 1)-game coloring numbers of the three product graphs. In particular, if one of the trees is a path, then we can similarly obtain the results of the (a, 1)-game coloring number of the product graph of tree and path.
文章引用：苏俊义. 乘积图的博弈染色数[J]. 应用数学进展, 2023, 12(4): 1504-1509. https://doi.org/10.12677/AAM.2023.124156

参考文献

[1] Bodlaender, H.L. (1991) On the Complexity of Some Coloring Games. In: M¨ohring, R.H., Ed., Graph-Theoretic Concepts in Computer Science. WG 1990. Lecture Notes in Computer Science, Vol. 484, Springer, Berlin, 30-40.
https://doi.org/10.1007/3-540-53832-1 29
[2] Faigle, U., Kern, U., Kierstead, H. and Trotter, W.T. (1993) On the Game Chromatic Number of Some Classes of Graphs. Ars Combinatoria, 35, 143-150.
[3] Zhu, X. (1999) The Game Coloring Number of Planar Graphs. Journal of Combinatorial Theory, Series B, 75, 245-258.
https://doi.org/10.1006/jctb.1998.1878
[4] Kierstead, H.A. (2005) Asymmetric Graph Coloring Games. Journal of Graph Theory, 48, 169-185.
https://doi.org/10.1002/jgt.20049
[5] Kierstead, H.A. and Yang, D. (2005) Very Asymmetric Marking Games. Order, 22, 93-107.
https://doi.org/10.1007/s11083-005-9012-y
[6] 刘佳丽. 树和路的乘积图的广义染色数及博弈染色数[J]. 应用数学进展, 2022, 11(1): 318-325.
https://doi.org/10.12677/AAM.2022.111039

为你推荐