Graph folding and chromatic number
-
Campena, Francis Joseph [1] ; Gervacio, Severino [1]
-
[1] La Salle University
La Salle University
City of Philadelphia, Estados Unidos
-
- Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 42, Nº. 4, 2023, págs. 957-965
- Idioma: inglés
- DOI: 10.22199/issn.0717-6279-5741
- Enlaces
-
Resumen
Given a connected graph G, identify two vertices if they have a common neighbor and then reduce the resulting multiple edges to simple edges. Repeat the process until the result is a complete graph. This process is called folding a graph.
We show here that any connected graph G which is not complete folds onto the connected graph Kp where p = χ(G), the chromatic number of G. Furthermore, the set of all integers p such that G folds onto Kp consist of consecutive integers, the smallest of which is χ(G).
One particular result of this study is that a sharp upper bound was obtained on the largest complete graph which a graph can be folded onto.
-
Referencias bibliográficas
- R. L. Brooks, “On colouring the nodes of a network”, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 37, pp. 194-197,...
- F. J. H. Campeña and S. V. Gervacio, “On the fold thickness of graphs”, Arabian Journal of Mathematics. https://doi.org10.1007/s40065-020-00276-z
- C. R. Cook, and A. B. Evans, Graph folding, In: Proceedings of the 10th South Eastern Conference on Combinatorics, Graph Theory, and Computing,...
- E. El-Kholy and A. El-Esawy, “Graph folding of some special graphs”, Journal of Mathematics and Statistics, vol. 1, no. 1, pp. 66-70, 2005....
- S. V. Gervacio, R. C. Guerrero, and H. M. Rara, “Folding wheels and fans”, Graphs and Combinatorics, vol. 18, no. 4, pp. 731-737, 2002. https://doi.org10.1007/s003730200058
- F. Harary, S. Hedetniemi, and G. Prins, “An Interpolation Theorem for Graphical Homomorphisms”, Portugalie Mathematica, vol. 20, pp. 453-462,...
