Graph powers and graph homomorphisms

zbMATH Open1215.05065arXiv0808.0362MaRDI QIDQ2380449FDOQ2380449

Authors: Hossein Hajiabolhassan, Ali Taherkhani 

Publication date: 26 March 2010

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

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.

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

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

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (22)

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