Circular chromatic number of induced subgraphs of Kneser graphs - Alishahi, Meysam (Ars mathematica contemporanea, 2018)
Študij enakosti kromatskega števila (barvitosti) in krožnega kromatskega števila grafov je v zadnjih desetletjih predstavljal aktiven tok raziskovanja. Tako sta Hajiabolhassan in Zhu leta 2003 dokazala, da če je ?$n$? dovolj velik glede na ?$k$?, potem ima Schrijverjev graf ?${\rm SG}(n,k)$? isto kromatsko in krožno kromatsko število. Kasneje so Meunier leta 2005 in neodvisno Simonyi in Tardos leta 2006 dokazali, da je ?$ξ({\rm SG}(n,k))=ξ_c({\rm SG}(n,k))$?, če je ?$n$? sod. V tem članku študiramo krožno kromatsko število induciranih podgrafov Kneserjevih grafov. Najprej posplošimo predhodne rezultate na ?$s$?-stabilne Kneserjeve grafe za velike sode ?$n$? in sode ?$s$?. Nadalje, kot posplošitev rezultata Hajiabolhassana in Zhuja pokažemo, da če je ?$n$? dovolj velik glede na ?$k$?, potem ima poljuben dovolj velik inducirani podgraf Kneserjevega grafa ?${\rm KG}(n,k)$? isto kromatsko število in krožno kromatsko število.
Keywords: Kneserjev graf; kromatsko število (barvitost); krožno kromatsko število; stabilen Kneserjev graf