dc.creator | Campena, Francis Joseph | |
dc.creator | Gervacio, Severino | |
dc.date | 2023-07-18 | |
dc.date.accessioned | 2023-07-21T14:31:38Z | |
dc.date.available | 2023-07-21T14:31:38Z | |
dc.identifier | https://www.revistaproyecciones.cl/index.php/proyecciones/article/view/5741 | |
dc.identifier | 10.22199/issn.0717-6279-5741 | |
dc.identifier.uri | https://revistaschilenas.uchile.cl/handle/2250/232392 | |
dc.description | 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. | en-US |
dc.format | application/pdf | |
dc.language | eng | |
dc.publisher | Universidad Católica del Norte. | en-US |
dc.relation | https://www.revistaproyecciones.cl/index.php/proyecciones/article/view/5741/4332 | |
dc.rights | Copyright (c) 2023 Francis Joseph Campena, Severino Gervacio | en-US |
dc.rights | https://creativecommons.org/licenses/by/4.0 | en-US |
dc.source | Proyecciones (Antofagasta, On line); Vol. 42 No. 4 (2023); 957-965 | en-US |
dc.source | Proyecciones. Revista de Matemática; Vol. 42 Núm. 4 (2023); 957-965 | es-ES |
dc.source | 0717-6279 | |
dc.source | 10.22199/issn.0717-6279-2023-04 | |
dc.subject | chromatic number | en-US |
dc.subject | folding | en-US |
dc.subject | bipartite graph | en-US |
dc.subject | complete graph | en-US |
dc.subject | 05C50 | en-US |
dc.subject | 05C76 | en-US |
dc.title | Graph folding and chromatic number | en-US |
dc.type | info:eu-repo/semantics/article | |
dc.type | info:eu-repo/semantics/publishedVersion | |
dc.type | text | en-US |