Circular coloring and Mycielski construction

DOI10.1016/J.DISC.2010.01.019zbMATH Open1221.05124arXiv0904.1319OpenAlexW2039612285MaRDI QIDQ968430FDOQ968430

Authors: Meysam Alishahi, Hossein Hajiabolhassan 

Publication date: 5 May 2010

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

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)$.

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

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

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)

Cites Work

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