Circular coloring and Mycielski construction

DOI10.1016/J.DISC.2010.01.019MaRDI QIDQ968430zbMATH OpenOpenAlexFDO

Authors Meysam Alishahi, Hossein Hajiabolhassan

Publication date 5 May 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringgraph homomorphismcircular coloringMycielski construction

Mathematics Subject Classification ID

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

Abstract: In this paper, we investigate circular chromatic number of Mycielski construction of graphs. It was shown in cite{MR2279672} that $t^{mth}$ Mycielskian of the Kneser graph $KG(m,n)$ has the same circular chromatic number and chromatic number provided that $m+t$ is an even integer. We prove that if $m$ is large enough, then $chi(M^t(KG(m,n)))=ch{i}_c(M^t(KG(m,n)))$ where $M^t$ is $t^{mth}$ Mycielskian. Also, we consider the generalized Kneser graph $KG(m,n,s)$ and show that there exists a threshold $m(n,s,t)$ such that $chi(M^t(KG(m,n,s)))=ch{i}_c(M^t(KG(m,n,s)))$ for $mgeqm(n,s,t)$.

Recommendations

• Circular chromatic number for iterated Mycielski graphs
• Circular chromatic number and Mycielski graphs
• Circular chromatic number and Mycielski construction
• Circular chromatic number and a generalization of the construction of Mycielski.
• Circular chromatic numbers of the generalized Mycielskians of cycles

Cites work

• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• A topological lower bound for the circular chromatic number of Schrijver graphs
• Circular chromatic number and Mycielski construction
• Circular chromatic number and Mycielski graphs
• Circular chromatic number for iterated Mycielski graphs
• Circular chromatic number of Kneser graphs
• Circular chromatic number: A survey
• Circular chromatic numbers of Mycielski's graphs
• Circular colouring and algebraic no-homomorphism theorems
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Kneser's conjecture, chromatic number, and homotopy
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Multichromatic numbers, star chromatic numbers and Kneser graphs
• On the chromatic number of the general Kneser-graph
• On the diameter of generalized Kneser graphs
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Star chromatic number
• Star chromatic numbers and products of graphs
• Sur le coloriage des graphs
• The circular chromatic number of the Mycielskian ofGdk
• The complete intersection theorem for systems of finite sets
• The exact bound in the Erdős-Ko-Rado theorem
• The odd girth of the generalised Kneser graph

Cited in

(10)

• On the chromatic number of general Kneser hypergraphs
• On Radial Colorings of Annuli
• A dichotomy theorem for circular colouring reconfiguration
• scientific article; zbMATH DE number 2157285 (Why is no real title available?)
• A generalization of Kneser's conjecture
• scientific article; zbMATH DE number 5139507 (Why is no real title available?)
• Circular chromatic number of induced subgraphs of Kneser graphs
• Circular chromatic number for iterated Mycielski graphs
• Non-cover generalized Mycielski, Kneser, and Schrijver graphs
• The circular altitude of a graph

This page was built for publication: Circular coloring and Mycielski construction

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