| Title: |
Graph Powers and Graph Homomorphisms |
| Authors: |
Hajiabolhassan, Hossein, Taherkhani, Ali |
| Publication Year: |
2008 |
| Collection: |
Mathematics |
| Subject Terms: |
Mathematics - Combinatorics |
| More Details: |
In this paper we investigate some basic properties of fractional powers. In this regard, we show that for any rational number $1\leq {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. |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/0808.0362 |
| Accession Number: |
edsarx.0808.0362 |
| Database: |
arXiv |
