Distinguishing graphs by total colourings - Kalinowski, Rafał (Ars mathematica contemporanea, 2016)
Vpeljemo totalno razlikovalno število ?$D^{′′}(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^′(G)$?, ki sta definirana za barvanja vozlišč oziroma povezav. Dobimo splošno ostro zgornjo mejo: ?$D^{′′}(G)≤ \lceil\sqrt{Δ(G)}\rceil$? za vsak povezan graf ?$G$?. Vpeljemo tudi totalno razlikovalno kromatsko število ?$χ^{′′}_D(G)$? definirano podobno za pravilna totalna barvanja grafa ?$G$?. Dokažemo, da je ?$χ^{′′}_{D}(G) ≤ χ^{′′}(G) + 1$? za vsak povezan graf ?$G$? s totalnim kromatskim številom ?$χ^{′′}(G)$?. Še več, če je ?$χ^{′′}(G) ≥Δ(G) + 2$?, potem je ?$χ^{′′}_{D}(G) = χ(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.
Keywords: symmetry breaking in graphs; total colourings of graphs; total distinguishing chromatic number; total distinguishing number; totalna barvanja grafov; totalno razlikovalno kromatsko število; totalno razlikovalno število; zlom simetrije v grafih