Planar graphs have bounded nonrepetitive chromatic number

2020
journal article
article
20
cris.lastimport.scopus2024-04-24T02:34:54Z
dc.abstract.enA colouring of a graph isnonrepetitiveif for every path of even order, thesequence of colours on the first half of the path is different from the sequence of colours onthe second half. We show that planar graphs have nonrepetitive colourings with a boundednumber of colours, thus proving a conjecture of Alon, Grytczuk, Hałuszczak and Riordan(2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding afixed minor, and graphs excluding a fixed topological minor.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.contributor.authorDujmović, Vidapl
dc.contributor.authorEsperet, Louispl
dc.contributor.authorJoret, Gwenaëlpl
dc.contributor.authorWalczak, Bartosz - 114113 pl
dc.contributor.authorWood, David R.pl
dc.date.accession2020-04-29pl
dc.date.accessioned2020-04-29T13:35:06Z
dc.date.available2020-04-29T13:35:06Z
dc.date.issued2020pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.physical1-11pl
dc.description.versionostateczna wersja wydawcy
dc.identifier.articleid2020:5pl
dc.identifier.doi10.19086/aic.12100pl
dc.identifier.issn2517-5599pl
dc.identifier.project2015/17/D/ST1/00585pl
dc.identifier.projectANR-16-CE40-0009-01 i ANR-18-CE40-0032pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/154938
dc.identifier.weblinkhttps://advances-in-combinatorics.scholasticahq.com/article/12100-planar-graphs-have-bounded-nonrepetitive-chromatic-numberpl
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subject.engraph colouringpl
dc.subject.ennonrepetitive colouringpl
dc.subject.enplanar graphpl
dc.subtypeArticlepl
dc.titlePlanar graphs have bounded nonrepetitive chromatic numberpl
dc.title.journalAdvances in Combinatoricspl
dc.typeJournalArticlepl
dspace.entity.typePublication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month