2015/01/26 by Amir Daneshgar, Daneshgar, Amir, Meysam Madani +1
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1501.06551
openalex publication_date 2015/01/26 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
A class of simple graphs such as cal G is said to be it\nodd-girth-closed if for any positive integer g there exists a graph G \∈\n cal G such that the odd-girth of G is greater than or equal to g. An\nodd-girth-closed class of graphs cal G is said to be it odd-pentagonal\nif there exists a positive integer g^* depending on cal G such that any\ngraph G \∈ cal G whose odd-girth is greater than g^* admits a\nhomomorphism to the five cycle (i.e. is C_5-colorable).\n In this article, we show that finding the odd girth of generalized Petersen\ngraphs can be transformed to an integer programming problem, and using this we\nexplicitly compute the odd girth of such graphs, showing that the class is\nodd-girth-closed. Also, motivated by showing that the class of generalized\nPetersen graphs is odd-pentagonal, we study the circular chromatic number of\nsuch graphs.\n