| dc.contributor.author | Bousquet, Nicolas | |
| dc.contributor.author | Esperet, Louis | |
| dc.contributor.author | Harutyunyan, Ararat | |
| dc.contributor.author | De Joannis de Verclos, Rémi | |
| dc.date.accessioned | 2019-11-26T11:26:09Z | |
| dc.date.available | 2019-11-26T11:26:09Z | |
| dc.date.issued | 2019 | |
| dc.identifier.issn | 1469-2163 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/20246 | |
| dc.language.iso | en | en |
| dc.subject | graph | en |
| dc.subject | trees | en |
| dc.subject.ddc | 519 | en |
| dc.title | Exact Distance Colouring in Trees | en |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | For 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.isversionofjnlname | Combinatorics, Probability and Computing | |
| dc.relation.isversionofjnlvol | 28 | en |
| dc.relation.isversionofjnlissue | 2 | en |
| dc.relation.isversionofjnldate | 2019-03 | |
| dc.relation.isversionofjnlpages | 177-186 | en |
| dc.relation.isversionofdoi | 10.1017/S0963548318000378 | en |
| dc.subject.ddclabel | Probabilités et mathématiques appliquées | en |
| dc.relation.forthcoming | non | en |
| dc.relation.forthcomingprint | non | en |
| dc.description.ssrncandidate | non | en |
| dc.description.halcandidate | oui | en |
| dc.description.readership | recherche | en |
| dc.description.audience | International | en |
| dc.relation.Isversionofjnlpeerreviewed | non | en |
| dc.relation.Isversionofjnlpeerreviewed | non | en |
| dc.date.updated | 2019-11-26T11:17:59Z | |
| hal.person.labIds | 74240 | |
| hal.person.labIds | 74240 | |
| hal.person.labIds | 989 | |
| hal.person.labIds | 115536 | |
| hal.identifier | hal-01525789 | * |
