Chromatic numbers of scalable graphs

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.

chromatic number, gluing and cloning operations, superposition, closed class, elemental and operational bases, constructive description

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.