Circular chromatic number of induced subgraphs of Kneser graphs

angleški

2018

letnik 15, številka 1

Kneserjev graf   kromatsko število (barvitost)   krožno kromatsko število   stabilen Kneserjev graf

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Š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 število.

29.05.2020