Graph powers and graph homomorphisms

MaRDI QIDQ2380449zbMATHFDO

Authors Hossein Hajiabolhassan, Ali Taherkhani

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0808.0362

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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

Recommendations

• On the circular chromatic number of graph powers
• On colorings of graph fractional powers
• Circular colouring and graph homomorphism
• Circular chromatic number: A survey
• Density and power graphs in graph homomorphism problem

Cited in

(22)

• On the multichromatic number of \(s\)-stable Kneser graphs
• On the circular chromatic number of graph powers
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• scientific article; zbMATH DE number 4189782 (Why is no real title available?)
• Generalized Powers of Graphs and Their Algorithmic Use
• Cartesian powers of graphs can be distinguished by two labels
• Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon
• Clawfreeness of the powers of a graph
• On the odd girth and the circular chromatic number of generalized Petersen graphs
• Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices
• Some relations between power graphs and Cayley graphs
• Hedetniemi's conjecture and adjoint functors in thin categories
• Iterated open neighborhood graphs and generalizations
• On cylindrical graph construction and its applications
• The inner power of a graph
• A generalization of Kneser's conjecture
• A combinatorial proof for the circular chromatic number of Kneser graphs
• Digraph functors which admit both left and right adjoints
• Density and power graphs in graph homomorphism problem
• Strengthening topological colorful results for graphs
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• Hedetniemi's conjecture and strongly multiplicative graphs

This page was built for publication: Graph powers and graph homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380449)