University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Online graph coloring with bichromatic exchanges

## Online graph coloring with bichromatic exchangesAdd to your list(s) Download to your calendar using vCal - Marc Heinrich (Université Lyon 1)
- Wednesday 13 June 2018, 15:00-16:00
- Watson LTA.
If you have a question about this talk, please contact Allan Lo. Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires $\Omega(\log n)$ colors in the worst case. We consider a variation of the First-Fit algorithm in which the algorithm is allowed to make modifications to previously colored vertices by performing local bichromatic exchanges. We show that such algorithms can be used to find an optimal coloring in the case of bipartite graphs, chordal graphs and outerplanar graphs. We also show that it can find coloring of general planar graphs with $O(\log \Delta)$ colors, where$\Delta$ is the maximum degree of the graph. The question of whether planar graphs can be colored by an online algorithm with bichromatic exchanges using only a constant number of colors is still open. This is a joint work with Sylvain Gravier. This talk is part of the Combinatorics and Probability Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsSchool of Mathematics Events 'Roles' Postgraduate Gender and Sexuality Network Discussion Theoretical computer science seminar## Other talks‘Using Consumer-Physics-Chemistry Interactions and Microstructural Design for Better Products’ The co-evolution of galaxies and supermassive black holes: the search for observational evidence of AGN feedback Applications and integration of semiconductor-based Metasurfaces Evaluation of sources of intelligence using a multi-armed bandit framework Irradiated brown dwarfs: Providing insights into exoplanet atmospheres Distinct degrees in induced subgraphs |