关于图的模染色数的上界
On the Upper Bound of Modular Chromatic Number of Graphs
摘要:
图的模染色是由邻点赋权导出的一种染色，是图的经典染色的一种推广。本文主要运用概率方法中的Lovasz局部引理，较大幅度地改进了关于图的模染色数的上界。
Abstract:
The modular coloring of a graph is induced by the weights of neighboring vertices. It is a generalization of the classic graph coloring. In this paper, we obtain a general upper bound for the modular chromatic number of graphs by using the Lovasz Local Lemma. Our result improves previous exponential bound significantly.
参考文献
|
[1]
|
徐俊明. 图论及其应用[M]. 第4版. 合肥: 中国科学技术大学出版社, 2019.
|
|
[2]
|
Karonski, M., Łuczak, T. and Thomason, A. (2004) Edge Weights and Vertex Colours. Journal of Combinatorial Theory, Series B, 91, 151-157. [Google Scholar] [CrossRef]
|
|
[3]
|
Kalkowski, M., Karonski, M. and Pfender, F. (2010) Vertex-Coloring Edge-Weightings: Towards the 1-2-3-Conjecture. Journal of Combinatorial Theory, Series B, 100, 347-349. [Google Scholar] [CrossRef]
|
|
[4]
|
Seamone, B. (2012) The 1-2-3 Conjecture and Related Problems: A Survey.
|
|
[5]
|
Czerwiski, S., Grytczuk, J. and Zelazny, W. (2009) Lucky Labelings of Graphs. Information Processing Letters, 109, 1078-1081. [Google Scholar] [CrossRef]
|
|
[6]
|
Ahadi, A., Dehghan, A., Kazemi, M. and Mollaahmadi, E. (2012) Computation of Lucky Number of Planar Graphs Is NP-Hard. Information Processing Letters, 112, 109-112. [Google Scholar] [CrossRef]
|
|
[7]
|
Okamoto, F., Salehi, E. and Zhang, P. (2010) A Checkerboard Problem and Modular Coloring of Graphs. Bulletin of the Institute of Combinatorics and Its Applications, 58, 29-47.
|
|
[8]
|
Zhang, P. (2016) A Kaleidoscopic View of Graph Colorings. Springer International Publishing, New York. [Google Scholar] [CrossRef]
|
|
[9]
|
Alon, N. and Spencer, J.H. (2000) The Probabilistic Method. 2nd Edition, Wiley-Interscience, New York. [Google Scholar] [CrossRef]
|