Graph Powers and Graph Homomorphisms

2008/08/04 by Hossein Hajiabolhassan, Hajiabolhassan, Hossein, Ali Taherkhani +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.0808.0362

arxiv created 2008/09/02 · arxiv updated 2009/12/01

Abstract

In this paper we investigate some basic properties of fractional powers. In this regard, we show that for any rational number 1≤ 2r+1\over 2s+1< og(G), G^{2r+1\over 2s+1}\longrightarrow H if and only if G\longrightarrow H^-2s+1\over 2r+1. Also, for two rational numbers 2r+1\over 2s+1 < 2p+1\over 2q+1 and a non-bipartite graph G, we show that G^{2r+1\over 2s+1} < G^{2p+1\over 2q+1}. In the sequel, we introduce an equivalent definition for circular chromatic number of graphs in terms of fractional powers. We also present a sufficient condition for equality of chromatic number and circular chromatic number.

Related

• On Coloring Properties of Graph Powers
• On coloring of fractional powers of graphs
• On Coloring of graph fractional powers
• Distinguishing number and distinguishing index of natural and fractional powers of graphs
• Fractional total colourings of graphs of high girth