Graph Powers and Graph Homomorphisms

Abstract

In this paper we investigate some basic properties of fractional powers. In this regard, we show that for any rational number $1\le \frac{2r+1}{2s+1}<og(G)$, $G^{\frac{2r+1}{2s+1}}⟶H$ if and only if $G⟶H^{-\frac{2s+1}{2r+1}}.$ Also, for two rational numbers $\frac{2r+1}{2s+1}<\frac{2p+1}{2q+1}$ and a non-bipartite graph $G$, we show that $G^{\frac{2r+1}{2s+1}}<G^{\frac{2p+1}{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.

References in corpus (1)

• On Colorings of Graph Powers