Хроматические числа масштабируемых графов

Рассматривается задача допустимой раскраски вершин в минимальное число цветов для связных неориентированных графов, не содержащих петель и кратных ребер. При каждом заданном $k \geqslant 3$ задача проверки существования допустимой вершинной раскраски графа в $k$ цветов является NP-полной. В связи с этим представляет интерес изучение процессов масштабирования графов с сохранением или ограничением их хроматических чисел. В работе исследуется характер изменения хроматического числа графов при увеличении числа вершин и ребер с помощью операций склейки графов путем отождествления их изоморфных подграфов. $G = (G_{1} \circ G_{2}) \tilde{G}$ — результирующий граф операции склейки графов $G_1$ и $G_2$, $\tilde{G} \subseteq G$ — подграф, полученный в результате отождествления изоморфных подграфов $G_1' \subseteq G_1$ и $G_2' \subseteq G_2$; $|V(G)| = |V(G_1)| + |V(G_2)| - |V(\tilde{G})|, |E(G)| = |E(G_1)| + |E(G_2)| - |E(\tilde{G})|$. Операции склейки, в которых один из графов $G_1$ или $G_2$ изоморфен другому графу или его подграфу и отождествление подграфов $G_1^{'}\subset G_1$ и $G_2^{'} \subset G_2$, проводится в соответствии с изоморфизмом $G_1' \cong G_2'$, называются операциями клонирования. На основе операций склейки и клонирования получено конструктивное описание класса 2-хроматических графов. Сформулированы ограничения на операции склейки и клонирования, обеспечивающие сохранение хроматического числа масштабируемых графов. Установлено, что при выполнении операций клонирования $\chi(G) =\max{\chi(G_1),\chi(G_2)}$. Приводятся примеры сборки 2-хроматических графов с использованием операций, удовлетворяющих этим ограничениям. Для произвольной операции склейки $\chi(G) \leqslant \max {\chi(G_1),\chi(G_2)} + |V(\tilde{G})| - |V(\tilde{G'})|$, где $\tilde{G'}$ — максимальный полный подграф в $\tilde{G}$. Оценивается возможный рост хроматического числа графов при масштабировании с различными ограничениями на суперпозиции операций склейки.

1. L. J. Stockmeyer, “Planar 3-colorability is NP-complete,” SIGACT News, vol. 5, no. 3, pp. 19–25, 1973.

2. M. R. Garey, D. S. Johnson, and S. L., “Some simplified NP-complete graph problems,” Theoretical Computer Science, vol. 1, no. 3, pp. 237–267, 1976.

3. G. Sabidussi, “Graphs with given group fnd given graph-theoretical properties,” Canadian Journal of Mathematics, vol. 9, pp. 515–525, 1957, doi: 10.4153/CJM-1957-060-7.

4. D. Geller and S. S., “The chromatic number and other functions of the lexicographic product,” Journal of Combinatorial Theory, vol. 19, pp. 87–95, 1975, doi: 10.1016/0095-8956(75)90076-3.

5. G. Ravindra and K. R. Parthasarathy, “Perfect product graphs,” Discrete Mathematics, vol. 20, no. 2, pp. 177–186, 1977, doi: 10.1016/0012-365X(77)90056-5.

6. K. Kuratowski, “Sur le problème des courbes gauches en Topologie,” Fundamenta Mathematicae, vol. 15, no. 1, pp. 271–283, 1930.

7. K. Wagner, “Über eine Eigenschaft der ebenen Komplexe,” Mathematische Annalen, vol. 114, no. 1, pp. 570–590, 1937.

8. N. Robertson and P. D. Seymour, “Graph minors. V. Excluding a planar graph,” Journal of Combinatorial Theory, Series B, vol. 41, no. 1, pp. 92–114, 1986, doi: 10.1016/0095-8956(86)90030-4.

9. N. Robertson and P. D. Seymour, “Graph Minors. XIII. The disjoint paths problem,” Journal of Combinatorial Theory, Series B, vol. 63, no. 1, pp. 65–110, 1995, doi: 10.1006/jctb.1995.1006.

10. N. Robertson and P. D. Seymour, “Graph Minors. XVI. Excluding a non-planar graph,” Journal of Combinatorial Theory, Series B, vol. 89, no. 1, pp. 43–76, 2003, doi: 10.1016/S0095-8956(03)00042-X.

11. N. Robertson and P. D. Seymour, “Graph Minors. XX. Wagner's conjecture,” Journal of Combinatorial Theory, Series B, vol. 92, no. 2, pp. 325–357, 2004, doi: 10.1016/j.jctb.2004.08.001.

12. M. A. Iordanski, “Constructive descriptions of graphs,” Discrete Analysis and Operations Research, vol. 3, no. 4, pp. 35–63, 1996.

13. M. A. Iordanski, Constructive graph theory and its applications. Cyrillic, 2016.

14. M. A. Iordanski, “Constructive Graph Theory: Generation Methods, Structure and Dynamic Characterization of Closed Classes of Graphs -- A survey.” 2020, doi: 10.48550/arXiv.2011.10984.

15. M. A. Iordanski, “Cloning of graphs,” in Proceedings of the XVIII International Conference on Problems of Theoretical Cybernetics, Penza, 2017, pp. 108–110.

16. M. A. Iordanski, “On the complexity of graph synthesis using cloning operations,” in Proceedings of the XIII International Seminar on Discrete Mathematics and Its Applications, 2019, pp. 220–223.

17. M. A. Iordanski, “Cloning operations and the diameter of graphs,” Discrete Mathematics, vol. 34, no. 2, pp. 26–31, 2022.

18. M. A. Iordanski, “Scaling Graphs with Constraint diameter,” Discrete Mathematics, vol. 35, no. 4, pp. 46–57, 2023.

19. M. A. Iordanski, “Dominant Sets with Neighborhood for Trees,” Modeling and Analysis of Information System, vol. 32, no. 1, pp. 32–41, 2025, doi: 10.18255/1818-1015-2025-1-32-41.

20. C. E. Leiserson, “Fat-trees: universal networks for hardware-efficient supercomputing,” IEEE Transactions on Computers, vol. C-34, pp. 892–901, 1985.

21. F. Harary, Theory of graphs. Mir, Moscow, 1973.