Рассматривается задача допустимой раскраски вершин в минимальное число цветов для связных неориентированных графов, не содержащих петель и кратных ребер. При каждом заданном $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}$. Оценивается возможный рост хроматического числа графов при масштабировании с различными ограничениями на суперпозиции операций склейки.
We consider the problem of feasible vertex coloring with the minimum number of colors for connected undirected graphs that contain no self-loops or multiple edges. For every given $k \geq 3$, the problem of checking the existence of a feasible vertex coloring of the graph with k colors is NP-complete. Therefore, studying graph-scaling processes while preserving or limiting their chromatic numbers is of interest. In this paper, we study the nature of changes in the chromatic number of graphs with an increase in the number of vertices and edges using gluing operations by identifying their isomorphic subgraphs. $G = (G_{1} \circ G_{2}) \tilde{G}$ — is the resulting graph of the gluing operation of graphs $G_1$ and $G_2$; $\tilde{G} \subseteq G$ is the subgraph obtained as a result of identifying isomorphic subgraphs $G_1' \subseteq G_1$ and $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})|$. Gluing operations in which one of the graphs $G_1$ or $G_2$ is isomorphic to another graph or its subgraph and the identification of subgraphs $G_1^{'}\subset G_1$ and $G_2^{'} \subset G_2$ is carried out in accordance with the isomorphism $G_1' \cong G_2'$, are called cloning operations. A constructive description of a class of 2-chromatic graphs is obtained based on the gluing and cloning operations. Constraints on the gluing and cloning operations that ensure the preservation of the chromatic number of scalable graphs are formulated. It is established that when performing cloning operations, $\chi(G) =\max{\chi(G_1),\chi(G_2)}$. Examples of assembling 2-chromatic graphs using operations satisfying these constraints are given. For an arbitrary gluing operation $\chi(G) \leqslant \max {\chi(G_1),\chi(G_2)} + |V(\tilde{G})| - |V(\tilde{G'})|$, where $\tilde{G'}$ is the maximal complete subgraph of $\tilde{G}$. The possible growth of the chromatic number of graphs is estimated when scaling with various restrictions on the superposition of gluing operations.
The authors declare that there are no conflicts of interest present.