Distinguishing graphs by total colourings

angleški

2016

letnik 11, številka 1

totalna barvanja grafov   totalno razlikovalno kromatsko število   totalno razlikovalno število   zlom simetrije v grafih

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

Vpeljemo totalno razlikovalno število ?$D^{\prime\prime}(G)$? grafa ?$G$? kot najmanjše takšno število ?$d$?, da ima ?$G$? totalno barvanje (ne nujno pravilno) z ?$d$? barvami, ki ga ohranja samo trivialni avtomorfizem. Gre za analogijo pojmov razlikovalnega števila ?$D(G)$? in razlikovalnega indeksa ?$D^\prime(G)$?, ki sta definirana za barvanja vozlišč oziroma povezav. Dobimo splošno ostro zgornjo mejo: ?$D^{\prime\prime}(G)\leq \lceil\sqrt{\Delta(G)}\rceil$? za vsak povezan graf ?$G$?. Vpeljemo tudi totalno razlikovalno kromatsko število ?$\chi^{\prime\prime}_D(G)$? definirano podobno za pravilna totalna barvanja grafa ?$G$?. Dokažemo, da je ?$\chi^{\prime\prime}_{D}(G) \leq \chi^{\prime\prime}(G) + 1$? za vsak povezan graf ?$G$? s totalnim kromatskim številom ?$\chi^{\prime\prime}(G)$?. Še več, če je ?$\chi^{\prime\prime}(G) \geq\Delta(G) + 2$?, potem je ?$\chi^{\prime\prime}_{D}(G) = \chi(G)$?. Te rezultate dokažemo tako da določimo ostre zgornje meje za minimalno število barv v pravilnem totalnem barvanju, v katerem iz vsakega vozlišča izhaja drugačna množica barvnih poti.

29.05.2020