|
|
乘积图的博弈染色数
|
Abstract:
本文讨论的图是两棵树的乘积图. 分别研究了树和树的笛卡尔积图、直积图和强积图的 (a, 1)-博弈染色数, 给出了三种乘积图的 (a, 1)-博弈染色的上界. 特殊地, 如果其中一棵树是一条路, 那么我们类似的可以得出关于树和路的乘积图的 (a, 1)-博弈染色数的结果.
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.
| [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 |
