Vertex transitive graphs G with chisub D(G) greater then chi(G) and small automorphism group - Balachandran, Niranjan (Ars mathematica contemporanea, 2019)
Za graf ?$G$? in pozitivno celo število ?$k$? se označitev vozlišč ?$f: V(G) → \{1, 2, …, k\}$? imenuje ?$k$?-razločevalna, če noben netrivialen avtomorfizem grafa ?$G$? ne ohranja množic ?$f^{-1}(i)$? za vsak ?$i \in \{1, …, k\}$?. Razločevalno kromatično število grafa ?$G$?, označeno z ?$χ_D(G)$?, je definirano kot najmanjše število ?$k$?, pri katerem obstaja ?$k$?-razločevalna označitev ?$V(G)$?, ki je tudi pravilno barvanje vozlišč grafa ?$G$?. V članku dokažemo naslednji izrek: Pri danem ?$k \in \mathbb{N}$? obstaja neskončno zaporedje vozliščno tranzitivnih grafov ?$G_i = (V_i, E_i)$?, za katere je (1.) ?$χ_D (G_i) > χ (G_i) > k$? in (2.) ?$|\rm{Aut}(G_i)| < 2k|V_i|$?, kjer ?$\rm{Aut}(G_i)$? označuje polno grupo avtomorfizmov grafa ?$G_i$?. To tudi odgovori na vprašanje, ki sta ga zastavila prvi in drugi avtor tega članka.
Keywords: Cayley graphs; Cayleyjevi grafi; distinguishing chromatic number; razločevalno kromatčno število; vertex transitive graphs; vozliščno tranzitivni grafi