ChisubD(G), |Aut(G)|, and a variant of the Motion Lemma - Balachandran, Niranjan (Ars mathematica contemporanea, 2017)
Razlikovalno kromatsko število grafa ?$G$?, označeno z ?${χ_D}(G)$?, je bilo najprej definirano kot minimalno število barv, potrebnih za pravilno barvanje grafa ?$G$?, pri katerem noben netrivialen avtomorfizem ?$φ$? 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 ?$χ_D(G) = χ(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 ?$χ_D(G) = χ(G) +1 $?, za poljubno velike vrednosti ?$χ(G)$?. (3.) opišemo netrivialne družine dvodelnih grafov, ki zadoščajo pogoju ?$χ D(G > r$? za vsako pozitivno celo število ?$r$?.
Keywords: grupa avtomorfizmov grafa; lema o gibanju; razlikovalno kromatsko število; šibki produkt grafov