ChisubD(G), |Aut(G)|, and a variant of the Motion Lemma

angleški

2017

letnik 12, številka 1

grupa avtomorfizmov grafa   lema o gibanju   razlikovalno kromatsko število   šibki produkt grafov

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

Razlikovalno kromatsko število grafa ?$G$?, označeno z ?${\chi_D}(G)$?, je bilo najprej definirano kot minimalno število barv, potrebnih za pravilno barvanje grafa ?$G$?, pri katerem noben netrivialen avtomorfizem ?$\phi$? grafa ?$G$? ne fiksira vsakega barvnega razreda grafa ?$G$?. V tem članku: (1.) dokažemo lemo, ki jo lahko imamo za različico leme o gibanju in z njeno pomočjo konstruiramo primere različnih družin grafov, ki zadoščajo pogoju ?$\chi_D(G) = \chi(G) +1 $?. (2.) podamo primer družin grafov, ki dopuščajo velike grupe avtomorfizmov, v katerih je vsako pravo barvanje razlikovalno. Opišemo tudi družine grafov z (relativno) zelo majhnimi grupami automorfizmov, ki zadoščajo pogoju ?$\chi_D(G) = \chi(G) +1 $?, za poljubno velike vrednosti ?$\chi(G)$?. (3.) opišemo netrivialne družine dvodelnih grafov, ki zadoščajo pogoju ?$\chi D(G > r$? za vsako pozitivno celo število ?$r$?.

29.05.2020