{"?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-RGSSIJL4/52880e14-68f9-4833-a83f-b67ffd43e728/PDF","dcterms:extent":"724 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-RGSSIJL4/2bd1ab02-88ad-4705-9788-be96606a77e6/TEXT","dcterms:extent":"55 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-RGSSIJL4","dcterms:isPartOf":[{"@rdf:resource":"https://www.dlib.si/details/URN:NBN:SI:spr-UP1WMFAR"},{"@xml:lang":"sl","#text":"Ars mathematica contemporanea"}],"dcterms:issued":"2017","dc:creator":["Balachandran, Niranjan","Padinhatteeri, Sajith"],"dc:format":[{"@xml:lang":"sl","#text":"številka:1"},{"@xml:lang":"sl","#text":"letnik:12"},{"@xml:lang":"sl","#text":"str. 89-109"}],"dc:identifier":["COBISSID:18095193","ISSN:1855-3966","URN:URN:NBN:SI:doc-RGSSIJL4"],"dc:language":"en","dc:publisher":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije"},"dc:subject":[{"@xml:lang":"sl","#text":"grupa avtomorfizmov grafa"},{"@xml:lang":"sl","#text":"lema o gibanju"},{"@xml:lang":"sl","#text":"razlikovalno kromatsko število"},{"@xml:lang":"sl","#text":"šibki produkt grafov"}],"dcterms:temporal":{"@rdf:resource":"2008-2025"},"dc:title":{"@xml:lang":"sl","#text":"ChisubD(G), |Aut(G)|, and a variant of the Motion Lemma|"},"dc:description":[{"@xml:lang":"sl","#text":"The Distinguishing Chromatic Number of a graph ?$G$?, denoted ?${\\chi_D}(G)$?, was first defined in K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), R16, as the minimum number of colors needed to properly color ?$G$? such that no non-trivial automorphism ?$\\phi$? of the graph ?$G$? fixes each color class of ?$G$?. In this paper, (1) We prove a lemma that may be considered a variant of the Motion lemma of A. Russell and R. Sundaram, A note on the asympotics and computational complexity of graph distinguishability, Electron. J. Combin. 5 (1998), R23 and use this to give examples of several families of graphs which satisfy ?$\\chi_D(G) = \\chi(G) +1$?. (2) We give an example of families of graphs that admit large automorphism groups in which every proper coloring is distinguishing. We also describe families of graphs with (relatively) very small automorphism groups which satisfy ?$\\chi_D(G) = \\chi(G + 1$?, for arbitrarily large values of ?$\\chi(G)$?. (3) We describe non-trivial families of bipartite graphs that satisfy ?$\\chi D(G > r$? for any positive integer ?$r$?"},{"@xml:lang":"sl","#text":"Razlikovalno kromatsko število grafa ?$G$?, označeno z ?${\\chi_D}(G)$?, je bilo najprej definirano kot minimalno število barv, potrebnih za pravilno barvanje grafa ?$G$?, pri katerem noben netrivialen avtomorfizem ?$\\phi$? 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 ?$\\chi_D(G) = \\chi(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 ?$\\chi_D(G) = \\chi(G) +1 $?, za poljubno velike vrednosti ?$\\chi(G)$?. (3.) opišemo netrivialne družine dvodelnih grafov, ki zadoščajo pogoju ?$\\chi D(G > r$? za vsako pozitivno celo število ?$r$?"}],"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-RGSSIJL4","edm:aggregatedCHO":{"@rdf:resource":"URN:NBN:SI:doc-RGSSIJL4"},"edm:isShownBy":{"@rdf:resource":"http://www.dlib.si/stream/URN:NBN:SI:doc-RGSSIJL4/52880e14-68f9-4833-a83f-b67ffd43e728/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-RGSSIJL4/maxi/edm"},"edm:isShownAt":{"@rdf:resource":"http://www.dlib.si/details/URN:NBN:SI:doc-RGSSIJL4"}}}}