Show simple item record

Graph folding and chromatic number

dc.creatorCampena, Francis Joseph
dc.creatorGervacio, Severino
dc.date2023-07-18
dc.date.accessioned2023-07-21T14:31:38Z
dc.date.available2023-07-21T14:31:38Z
dc.identifierhttps://www.revistaproyecciones.cl/index.php/proyecciones/article/view/5741
dc.identifier10.22199/issn.0717-6279-5741
dc.identifier.urihttps://revistaschilenas.uchile.cl/handle/2250/232392
dc.descriptionGiven 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.formatapplication/pdf
dc.languageeng
dc.publisherUniversidad Católica del Norte.en-US
dc.relationhttps://www.revistaproyecciones.cl/index.php/proyecciones/article/view/5741/4332
dc.rightsCopyright (c) 2023 Francis Joseph Campena, Severino Gervacioen-US
dc.rightshttps://creativecommons.org/licenses/by/4.0en-US
dc.sourceProyecciones (Antofagasta, On line); Vol. 42 No. 4 (2023); 957-965en-US
dc.sourceProyecciones. Revista de Matemática; Vol. 42 Núm. 4 (2023); 957-965es-ES
dc.source0717-6279
dc.source10.22199/issn.0717-6279-2023-04
dc.subjectchromatic numberen-US
dc.subjectfoldingen-US
dc.subjectbipartite graphen-US
dc.subjectcomplete graphen-US
dc.subject05C50en-US
dc.subject05C76en-US
dc.titleGraph folding and chromatic numberen-US
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion
dc.typetexten-US


This item appears in the following Collection(s)

Show simple item record