Уникальная возможность отображения списка полных трехсторонних графиков
https://doi.org/10.22405/2226-8383-2022-23-2-170-178
Аннотация
Учитывая список 𝐿(𝑣) для каждой вершины 𝑣, мы говорим, что граф 𝐺 является 𝐿- раскрашиваемым, если существует правильная раскраска вершины G, где каждая вершина
𝑣 берет свой цвет из 𝐿(𝑣). Граф является однозначно раскрашиваемым списком 𝑘, если существует присвоение списка 𝐿 такое, что |𝐿(𝑣)| = 𝑘 для каждой вершины 𝑣, и граф имеет ровно одну раскраску 𝐿 с этими списками. Если граф 𝐺 не является однозначно раскрашиваемым списком 𝑘, мы также говорим, что 𝐺 обладает свойством 𝑀(𝑘). Наименьшее
целое число 𝑘, такое, что 𝐺 обладает свойством 𝑀(𝑘), называется 𝑚-числом 𝐺, обозначаемым 𝑚(𝐺). В этой статье сначала мы охарактеризуем свойство полных трехсторонних
графов, когда это однозначно 𝑘-список раскрашиваемых графов, наконец, мы докажем, что 𝑚(𝐾2,2,𝑚) = 𝑚(𝐾2,3,𝑛) = 𝑚(𝐾2,4,𝑝) = 𝑚(𝐾3,3,3) = 4 за каждые 𝑚 > 9, 𝑛 > 5, 𝑝 > 4.
Список литературы
1. M. Behzad, Graphs and thei chromatic number, Doctoral Thesis (Michigan State University), 1965.
2. M. Behzad and G. Chartrand, Introduction to the theory of graphs, Allyn and Bacon, Boston,1971.
3. M. Behzad, G. Chartrand and J. Cooper, The coloring numbers of complete graphs, J. London Math. Soc. № 42 (1967), 226 – 228.
4. J.A. Bondy and U.S.R. Murty, Graph theory with applications, MacMillan, 1976.
5. R. Diestel, Graph Theory, Springer – Verlag New Youk, 2000.
6. J.H. Dinitz and W.J. Martin, The stipulation polynomial of a uniquely list colorable graph, Austran. J. Combin. № 11 (1995) 105–115.
7. P. Erd¨os, A. L. Rubin, and H. Taylor. Choosability in graphs. In Proceedings of west coast conference on combinatorics, graph theory, and computing, number 26 in Congr. Numer., pages 125–157, Arcata, CA, September 1979.
8. M. Ghebleh and E.S. Mahmoodian, On uniquely list colorable graphs, Ars Combin. № 59 (2001) 307–318.
9. Le Xuan Hung, Colorings of the graph 𝐾𝑚 2 + 𝐾𝑛, Journal of Siberian Federal University. Mathematics & Physics, to appear.
10. M. Mahdian and E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. № 51 (1999) 295–305.
11. R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory № 4 (1968) 52–71.
12. Ngo Dac Tan and Le Xuan Hung, On colorings of split graphs, Acta Mathematica Vietnammica, Vol. 31, № 3, 2006, pp. 195 – 204.
13. V.G. Vizing, On an estimate of the chromatic class of a 𝑝-graph, Discret. Analiz. № 3 (1964), pp. 23–30. (In Russian)
14. V. G. Vizing. Coloring the vertices of a graph in prescribed colors. In Diskret. Analiz, № 29 in Metody Diskret. Anal. v Teorii Kodov i Shem, pp. 3–10, 1976.
15. W. Wang and X. Liu, List-coloring based channel allocation for open-spectrum wireless networks, in Proceedings of the IEEE International Conference on Vehicular Technology (VTC
16. ’05), 2005, pp. 690 – 694.
17. R.J. Wilson, Introduction to graph theory, Longman group ltd, London, (1975).
18. Yancai Zhao and Erfang Shan, On characterization of uniquely 3-list colorable complete multipartite graphs, Discussiones Mathematicae Graph Theory, № 30, 2010, pp. 105–114.
19. Y.Q. Zhao, W.J. He, Y.F. Shen and Y.N. Wang, Note on characterization of uniquely 3- list colorable complete multipartite graphs, in: Discrete Geometry, Combinatorics and Graph Theory, LNCS 4381 (Springer, Berlin, 2007, pp. 278–287.
Рецензия
Для цитирования:
Хонг В. Уникальная возможность отображения списка полных трехсторонних графиков. Чебышевский сборник. 2022;23(2):170-178. https://doi.org/10.22405/2226-8383-2022-23-2-170-178
For citation:
Hung X. Uniquely list colorability of complete tripartite graphs. Chebyshevskii Sbornik. 2022;23(2):170-178. (In Russ.) https://doi.org/10.22405/2226-8383-2022-23-2-170-178
Просмотров: 144
Послать статью по эл. почте 