Graph powers and graph homomorphisms

Hossein Hajiabolhassan ; Ali Taherkhani

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

In this paper, we investigate some basic properties of fractional powers. In this regard, we show that for any non-bipartite graph $G$ and positive rational numbers ${2r+1\over 2s+1} < {2p+1\over 2q+1}$, we have $G^{2r+1\over 2s+1} < G^{2p+1\over 2q+1}$. Next, we study the power thickness of $G$, that is, the supremum of rational numbers ${2r+1\over 2s+1}$ such that $G$ and $G^{2r+1\over 2s+1}$ have the same chromatic number. We prove that the power thickness of any non-complete circular complete graph is greater than one. This provides a sufficient condition for the equality of the chromatic number and the circular chromatic number of graphs. Finally, we introduce an equivalent definition for the circular chromatic number of graphs in terms of fractional powers. Also, we show that for any non-bipartite graph $G$ if $0 < {{2r+1}\over {2s+1}} \leq {{\chi(G)}\over{3(\chi(G)-2)}}$, then $\chi(G^{{2r+1}\over {2s+1}})=3$. Moreover, $\chi(G)\neq\chi_c(G)$ if and only if there exists a rational number ${{2r+1}\over {2s+1}}>{{\chi(G)}\over{3(\chi(G)-2)}}$ for which $\chi(G^{{2r+1}\over {2s+1}})= 3$.

Détail

DOI : 10.37236/289

Classification : 05C15