Coloring properties of categorical product of general Kneser hypergraphs

angleški

2018

letnik 15, številka 1

barvitost   Hedetniemijeva domneva   kategorični produkt   kromatično število   splošni Kneserjev hipergraf

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

Pred več kot 50 leti je Hedetniemi postavil domnevo, da je barvitost (kromatično število) kategoričnega produkta dveh grafov enako minimumu njunih barvitosti. Ta domneva je bila v zadnjih letih deležna precejšnje pozornosti. Hedetniemijevo domnevo je leta 1992 Zhu posplošil na hipergrafe. Hajiabolhassan in Meunier sta leta 2016 predstavila prvo netrivialno spodnjo mejo za barvitost kategoričnega produkta splošnih Kneserjevih hipergrafov in z uporabo te spodnje meje sta potrdila resničnost Zhujeve domneve za nekaj družin hipergrafov. V tem članku predstavimo nekaj rezultatov o barvitosti kategoričnega produkta splošnih Kneserjevih hipergrafov, ki so posplošitev rezultata Hajiabolhassana in Meunierja. Prav tako predstavimo novo spodnjo mejo za barvitost kategoričnega produkta splošnih Kneserjevih hipergrafov, ki je lahko mnogo boljša od spodnje meje Hajiabolhassana in Meunierja. Z uporabo te spodnje meje obogatimo družino hipergrafov, ki zadoščajo Zhujevi domnevi.

29.05.2020