Show simple item record

dc.contributor.authorBousquet, Nicolas
dc.contributor.authorEsperet, Louis
dc.contributor.authorHarutyunyan, Ararat
dc.contributor.authorDe Joannis de Verclos, Rémi
dc.date.accessioned2019-11-26T11:26:09Z
dc.date.available2019-11-26T11:26:09Z
dc.date.issued2019
dc.identifier.issn1469-2163
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20246
dc.language.isoenen
dc.subjectgraphen
dc.subjecttreesen
dc.subject.ddc519en
dc.titleExact Distance Colouring in Treesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenFor an integer q ⩾ 2 and an even integer d, consider the graph obtained from a large complete q-ary tree by connecting with an edge any two vertices at distance exactly d in the tree. This graph has clique number q + 1, and the purpose of this short note is to prove that its chromatic number is Θ((d log q)/log d). It was not known that the chromatic number of this graph grows with d. As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant C such that for any odd integer d, any planar graph can be coloured with at most C colours such that any pair of vertices at distance exactly d have distinct colours. Finally, we study interval colouring of trees (where vertices at distance at least d and at most cd, for some real c > 1, must be assigned distinct colours), giving a sharp upper bound in the case of bounded degree trees.en
dc.relation.isversionofjnlnameCombinatorics, Probability and Computing
dc.relation.isversionofjnlvol28en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2019-03
dc.relation.isversionofjnlpages177-186en
dc.relation.isversionofdoi10.1017/S0963548318000378en
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-11-26T11:17:59Z
hal.person.labIds74240
hal.person.labIds74240
hal.person.labIds989
hal.person.labIds115536
hal.identifierhal-01525789*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record