{"?xml":{"@version":"1.0"},"edm:RDF":{"@xmlns:dc":"http://purl.org/dc/elements/1.1/","@xmlns:edm":"http://www.europeana.eu/schemas/edm/","@xmlns:wgs84_pos":"http://www.w3.org/2003/01/geo/wgs84_pos","@xmlns:foaf":"http://xmlns.com/foaf/0.1/","@xmlns:rdaGr2":"http://rdvocab.info/ElementsGr2","@xmlns:oai":"http://www.openarchives.org/OAI/2.0/","@xmlns:owl":"http://www.w3.org/2002/07/owl#","@xmlns:rdf":"http://www.w3.org/1999/02/22-rdf-syntax-ns#","@xmlns:ore":"http://www.openarchives.org/ore/terms/","@xmlns:skos":"http://www.w3.org/2004/02/skos/core#","@xmlns:dcterms":"http://purl.org/dc/terms/","edm:WebResource":[{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-12L1O0R1/33798125-8c74-403e-aac6-6ed304cb2c05/PDF","dcterms:extent":"280 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-12L1O0R1/b5a9e7d8-9a97-48b1-bb05-7763a4098e3b/TEXT","dcterms:extent":"28 KB"}],"edm:TimeSpan":{"@rdf:about":"2008-2025","edm:begin":{"@xml:lang":"en","#text":"2008"},"edm:end":{"@xml:lang":"en","#text":"2025"}},"edm:ProvidedCHO":{"@rdf:about":"URN:NBN:SI:doc-12L1O0R1","dcterms:isPartOf":[{"@rdf:resource":"https://www.dlib.si/details/URN:NBN:SI:spr-UP1WMFAR"},{"@xml:lang":"sl","#text":"Ars mathematica contemporanea"}],"dcterms:issued":"2016","dc:creator":["Kalinowski, Rafał","Pilśniak, Monika","Woźniak, Mariusz"],"dc:format":[{"@xml:lang":"sl","#text":"številka:1"},{"@xml:lang":"sl","#text":"letnik:11"},{"@xml:lang":"sl","#text":"str. 79-89"}],"dc:identifier":["COBISSID:17841241","ISSN:1855-3966","URN:URN:NBN:SI:doc-12L1O0R1"],"dc:language":"en","dc:publisher":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije"},"dc:subject":[{"@xml:lang":"en","#text":"symmetry breaking in graphs"},{"@xml:lang":"en","#text":"total colourings of graphs"},{"@xml:lang":"en","#text":"total distinguishing chromatic number"},{"@xml:lang":"en","#text":"total distinguishing number"},{"@xml:lang":"sl","#text":"totalna barvanja grafov"},{"@xml:lang":"sl","#text":"totalno razlikovalno kromatsko število"},{"@xml:lang":"sl","#text":"totalno razlikovalno število"},{"@xml:lang":"sl","#text":"zlom simetrije v grafih"}],"dcterms:temporal":{"@rdf:resource":"2008-2025"},"dc:title":{"@xml:lang":"sl","#text":"Distinguishing graphs by total colourings|"},"dc:description":[{"@xml:lang":"sl","#text":"We introduce the total distinguishing number ?$D^{\\prime\\prime}(G)$? of a graph ?$G$? as the least number ?$d$? such that ?$G$? has a total colouring (not necessarily proper) with ?$d$? colours that is only preserved by the trivial automorphism. This is an analog to the notion of the distinguishing number ?$D(G)$?, and the distinguishing index ?$D^\\prime(G)$?, which are defined for colourings of vertices and edges, respectively. We obtain a general sharp upper bound: ?$D^{\\prime\\prime}(G)\\leq \\lceil\\sqrt{\\Delta(G)}\\rceil$? for every connected graph ?$G$?. We also introduce the total distinguishing chromatic number ?$\\chi^{\\prime\\prime}_D(G)$? similarly defined for proper total colourings of a graph ?$G$?. We prove that ?$\\chi^{\\prime\\prime}_{D}(G) \\leq \\chi^{\\prime\\prime}(G) + 1$? for every connected graph ?$G$? with the total chromatic number ?$\\chi^{\\prime\\prime}(G)$?. Moreover, if ?$\\chi^{\\prime\\prime}(G) \\geq\\Delta(G) + 2$?, then ?$\\chi^{\\prime\\prime}_{D}(G) = \\chi(G)$?. We prove these results by setting sharp upper bounds for the minimal number of colours in a proper total colouring such that each vertex has a distinct set of colour walks emanating from it"},{"@xml:lang":"sl","#text":"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"}],"edm:type":"TEXT","dc:type":[{"@xml:lang":"sl","#text":"znanstveno časopisje"},{"@xml:lang":"en","#text":"journals"},{"@rdf:resource":"http://www.wikidata.org/entity/Q361785"}]},"ore:Aggregation":{"@rdf:about":"http://www.dlib.si/?URN=URN:NBN:SI:doc-12L1O0R1","edm:aggregatedCHO":{"@rdf:resource":"URN:NBN:SI:doc-12L1O0R1"},"edm:isShownBy":{"@rdf:resource":"http://www.dlib.si/stream/URN:NBN:SI:doc-12L1O0R1/33798125-8c74-403e-aac6-6ed304cb2c05/PDF"},"edm:rights":{"@rdf:resource":"http://creativecommons.org/licenses/by/4.0/"},"edm:provider":"Slovenian National E-content Aggregator","edm:intermediateProvider":{"@xml:lang":"en","#text":"National and University Library of Slovenia"},"edm:dataProvider":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije"},"edm:object":{"@rdf:resource":"http://www.dlib.si/streamdb/URN:NBN:SI:doc-12L1O0R1/maxi/edm"},"edm:isShownAt":{"@rdf:resource":"http://www.dlib.si/details/URN:NBN:SI:doc-12L1O0R1"}}}}