333 KB34 KB200820252018Alishahi, MeysamTaherkhani, Alištevilka:1letnik:15str. 161-172COBISSID:18485849ISSN:1855-3966URN:URN:NBN:SI:doc-P0XUUJ4VenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaKneserjev grafkromatsko število (barvitost)krožno kromatsko številostabilen Kneserjev grafCircular chromatic number of induced subgraphs of Kneser graphs|Š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 ?$\xi({\rm SG}(n,k))=\xi_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 številoTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije