On colorings of graph powers

DOI10.1016/j.disc.2009.01.004zbMath1213.05082arXiv0708.0704OpenAlexW2077206408MaRDI QIDQ1043947

Hossein Hajiabolhassan

Publication date: 10 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringgraph homomorphismcircular coloringhelical graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

On the odd girth and the circular chromatic number of generalized Petersen graphs ⋮ Dynamic coloring of graphs having no \(K_5\) minor ⋮ The chromatic number of the product of 14-chromatic graphs can be 13 ⋮ On multichromatic numbers of widely colorable graphs ⋮ Clawfreeness of the powers of a graph ⋮ On the two largest distance eigenvalues of graph powers ⋮ Hedetniemi's conjecture and adjoint functors in thin categories ⋮ On colorings of graph fractional powers ⋮ Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number ⋮ On the least distance eigenvalues of the second power of a graph ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ On the connectivity of k-distance graphs ⋮ On inverse powers of graphs and topological implications of Hedetniemi's conjecture ⋮ On the Circular Chromatic Number of Graph Powers ⋮ Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• Graph homomorphisms and nodal domains
• Homomorphisms and edge-colourings of planar graphs
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Density and power graphs in graph homomorphism problem
• Coloring graphs with locally few colors
• Circular chromatic number of Kneser graphs
• Topological lower bounds for the chromatic number: a hierarchy
• Random cubic graphs are not homomorphic to the cycle of size 7
• Regular graphs with no homomorphisms onto cycles
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Homomorphism bounded classes of graphs
• Circular colouring and algebraic no-homomorphism theorems
• Colorful subgraphs in Kneser-like graphs
• Local chromatic number and Sperner capacity
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• The Fractional Chromatic Number of Graphs of Maximum Degree at Most Three
• Circular chromatic numbers of some reduced Kneser graphs
• Star chromatic number
• Multichromatic numbers, star chromatic numbers and Kneser graphs
• Graph homomorphisms through random walks
• On graphs with strongly independent color-classes
• A topological lower bound for the circular chromatic number of Schrijver graphs
• Circular chromatic number: A survey
• A new proof of the independence ratio of triangle-free cubic graphs
• Colorings and homomorphisms of degenerate and bounded degree graphs