chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2022-23-2-170-178cheb-1278Research ArticleСтатьиArticleУникальная возможность отображения списка полных трехсторонних графиковUniquely list colorability of complete tripartite graphsХонгВан ЛеHungXuan Lelxhung@hunre.edu.vnХанойский университет природных ресурсов и окружающей средыВьетнамHanoi University for Natural Resources and EnvironmentViet Nam202208072022232170178Copyright © Хонг В., 20222022Хонг В.Hung X.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1278

Учитывая список 𝐿(𝑣) для каждой вершины 𝑣, мы говорим, что граф 𝐺 является 𝐿- раскрашиваемым, если существует правильная раскраска вершины G, где каждая вершина𝑣 берет свой цвет из 𝐿(𝑣). Граф является однозначно раскрашиваемым списком 𝑘, если существует присвоение списка 𝐿 такое, что |𝐿(𝑣)| = 𝑘 для каждой вершины 𝑣, и граф имеет ровно одну раскраску 𝐿 с этими списками. Если граф 𝐺 не является однозначно раскрашиваемым списком 𝑘, мы также говорим, что 𝐺 обладает свойством 𝑀(𝑘). Наименьшеецелое число 𝑘, такое, что 𝐺 обладает свойством 𝑀(𝑘), называется 𝑚-числом 𝐺, обозначаемым 𝑚(𝐺). В этой статье сначала мы охарактеризуем свойство полных трехстороннихграфов, когда это однозначно 𝑘-список раскрашиваемых графов, наконец, мы докажем, что 𝑚(𝐾2,2,𝑚) = 𝑚(𝐾2,3,𝑛) = 𝑚(𝐾2,4,𝑝) = 𝑚(𝐾3,3,3) = 4 за каждые 𝑚 > 9, 𝑛 > 5, 𝑝 > 4.

Given a list 𝐿(𝑣) for each vertex 𝑣, we say that the graph 𝐺 is 𝐿-colorable if there is a proper vertex coloring of G where each vertex 𝑣 takes its color from 𝐿(𝑣). The graph is uniquely 𝑘-listcolorable if there is a list assignment 𝐿 such that |𝐿(𝑣)| = 𝑘 for every vertex 𝑣 and the graph has exactly one 𝐿-coloring with these lists. If a graph 𝐺 is not uniquely 𝑘-list colorable, we alsosay that 𝐺 has property 𝑀(𝑘). The least integer 𝑘 such that 𝐺 has the property 𝑀(𝑘) is called the 𝑚-number of 𝐺, denoted by 𝑚(𝐺). In this paper, first we characterize about the property ofthe complete tripartite graphs when it is uniquely 𝑘-list colorable graphs, finally we shall prove that 𝑚(𝐾2,2,𝑚) = 𝑚(𝐾2,3,𝑛) = 𝑚(𝐾2,4,𝑝) = 𝑚(𝐾3,3,3) = 4 for every 𝑚 > 9, 𝑛 > 5, 𝑝 > 4.

Раскраска вершин (раскраска)раскраска спискаоднозначно раскра- шиваемый список графовполный r-частичный граф.Vertex coloring (coloring)list coloringuniquely list colorable graphcomplete r-partite graph.ReferencesM. Behzad, Graphs and thei chromatic number, Doctoral Thesis (Michigan State University), 1965.M. Behzad, 1965, “Graphs and thei chromatic number”, Doctoral Thesis (Michigan State University).M. Behzad and G. Chartrand, Introduction to the theory of graphs, Allyn and Bacon, Boston,1971.M. Behzad and G. Chartrand, 1971, “Introduction to the theory of graphs”, Allyn and Bacon, Boston.M. Behzad, G. Chartrand and J. Cooper, The coloring numbers of complete graphs, J. London Math. Soc. № 42 (1967), 226 – 228.M. Behzad, G. Chartrand and J. Cooper, 1967, “The coloring numbers of complete graphs”, J. London Math. Soc. № 42, pp. 226 – 228.J.A. Bondy and U.S.R. Murty, Graph theory with applications, MacMillan, 1976.J.A. Bondy and U.S.R. Murty, 1976, “Graph theory with applications”, MacMillan.R. Diestel, Graph Theory, Springer – Verlag New Youk, 2000.R. Diestel, 2000, “Graph Theory”, Springer – Verlag New York.J.H. Dinitz and W.J. Martin, The stipulation polynomial of a uniquely list colorable graph, Austran. J. Combin. № 11 (1995) 105–115.J.H. Dinitz and W.J. Martin, 1995, “The stipulation polynomial of a uniquely list colorable graph”, Austran. J. Combin. № 11, pp. 105–115.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.P. Erd¨os, A. L. Rubin, and H. Taylor, 1979, “Choosability in graphs”. In Proceedings of west coast conference on combinatorics, graph theory, and computing, number 26 in Congr. Numer., pp. 125–157, Arcata, CA.M. Ghebleh and E.S. Mahmoodian, On uniquely list colorable graphs, Ars Combin. № 59 (2001) 307–318.M. Ghebleh and E.S. Mahmoodian, 2001, “On uniquely list colorable graphs”, Ars Combin. № 59, pp. 307–318.Le Xuan Hung, Colorings of the graph 𝐾𝑚 2 + 𝐾𝑛, Journal of Siberian Federal University. Mathematics & Physics, to appear.Le Xuan Hung, “Colorings of the graph 𝐾𝑚2 + 𝐾𝑛”, Journal of Siberian Federal University. Mathematics & Physics, to appear.M. Mahdian and E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. № 51 (1999) 295–305.M. Mahdian and E.S. Mahmoodian, 1999, “A haracterization of uniquely 2-list colorable graphs”, Ars Combin. № 51, pp. 295–305.R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory № 4 (1968) 52–71.R.C. Read, 1968, “An introduction to chromatic polynomials”, J. Combin. Theory, № 4, pp. 52–71.Ngo Dac Tan and Le Xuan Hung, On colorings of split graphs, Acta Mathematica Vietnammica, Vol. 31, № 3, 2006, pp. 195 – 204.Ngo Dac Tan and Le Xuan Hung, 2006, “On colorings of split graphs”, Acta Mathematica Vietnammica, Volume 31, № 3, pp. 195 – 204.V.G. Vizing, On an estimate of the chromatic class of a 𝑝-graph, Discret. Analiz. № 3 (1964), pp. 23–30. (In Russian)V.G. Vizing, 1964, “On an estimate of the chromatic class of a 𝑝-graph”, Discret. Analiz. № 3, pp. 23–30. (In Russian).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.V. G. Vizing ,1976, “Coloring the vertices of a graph in prescribed colors”. In Diskret. Analiz, number 29 in Metody Diskret. Anal. v Teorii Kodov i Shem, pp. 3–10.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 (VTCW. Wang and X. Liu, 2005, “List-coloring based channel allocation for open-spectrum wireless networks’05), 2005, pp. 690 – 694., in Proceedings of the IEEE International Conference on Vehicular Technology (VTC ’05), pp. 690 – 694.R.J. Wilson, Introduction to graph theory, Longman group ltd, London, (1975).R.J. Wilson, 1975, Introduction to graph theory, Longman group ltd, London.Yancai Zhao and Erfang Shan, On characterization of uniquely 3-list colorable complete multipartite graphs, Discussiones Mathematicae Graph Theory, № 30, 2010, pp. 105–114.Yancai Zhao and Erfang Shan, 2010, “On characterization of uniquely 3-list colorable complete multipartite graphs”, Discussiones Mathematicae Graph Theory, № 30, pp. 105–114.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.Y.Q. Zhao, W.J. He, Y.F. Shen and Y.N. Wang, 2007, “Note on characterization of uniquely 3-list colorable complete multipartite graphs”, in: Discrete Geometry, Combinatorics and Graph Theory, LNCS 4381 (Springer, Berlin, pp. 278–287.

The authors declare that there are no conflicts of interest present.