Distance-two colorings of graphs
dc.contributor.author | ESPERET, Louis | |
dc.date | 2008-05-30 | |
dc.date.accessioned | 2021-01-13T14:02:52Z | |
dc.date.available | 2021-01-13T14:02:52Z | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/25100 | |
dc.description.abstract | Dans cette thèse, on s’intéresse en particulier à la coloration du carré des graphes planaires (deux sommets à distance au plus deux ont des couleurs distinctes) et à la coloration cyclique des graphes planaires (deux sommets incidents à la même face ont des couleurs distinctes). On montre un résultat général qui implique que deux conjectures importantes sur ces colorations (Wegner 1977 et Borodin 1984) sont vraies asymptotiquement. On s’intéresse également à d’autres colorations à distance deux, qui ont des liens (plus ou moins vagues) avec l’allocation de fréquences dans les réseaux radios, la théorie des jeux, la sociologie et l’écologie. | |
dc.description.abstractEn | In this thesis, we study the colouring of the square of planar graphs (two vertices at distance at most two receive distinct colours) and the cyclic colouring of plane graphs (two vertices incident to the same face receive distinct colours). We show a general result implying that two important conjectures on these colourings (Wegner 1977 and Borodin 1984) hold asymptotically. We also study other types of distance-two colourings, (more or less related to frequency assignment in radio networks, game theory, sociology and ecology. | |
dc.format | application/pdf | |
dc.language.iso | EN | |
dc.rights | free | |
dc.subject | Informatique | |
dc.subject | Théorie des graphes | |
dc.subject | coloration de graphes | |
dc.subject | graphes planaires | |
dc.title | Distance-two colorings of graphs | |
dc.type | Thèses de doctorat | |
bordeaux.hal.laboratories | Thèses Bordeaux 1 Ori-Oai | * |
bordeaux.institution | Université de Bordeaux | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Distance-two%20colorings%20of%20graphs&rft.atitle=Distance-two%20colorings%20of%20graphs&rft.au=ESPERET,%20Louis&rft.genre=unknown |