Seminar of Theoretical Computer Science - Róbert Lukoťka

Friday 11.5.2018 at 11:00, Lecture room M/213

---

Róbert Lukoťka:
Deciding 3-edge-colourability of graphs

Abstract:
We present three ideas that can be used to improve running times of algorithms deciding 3-edge-colorability of graphs. We show two ways how to efficiently transform a 3-edge-coloring into an improper 2-vertex coloring using balanced valuations [F. Jaeger: Balanced Valuations and Flows in Multigraphs, Proceedings of the American Mathematical Society 55 (1976)] or embeddings into orientable surfaces. Finally, we sketch how Hilbert's Nullstellensatz can be used to provide a certificate that a graph is not 3-edge-colourable [J. A. De Loera, J. Lee, P. N. Malkin, S. Margulies: Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz, Journal of Symbolic Computation 46 (2011), 1260-1283]. 

 

web: http://kedrigern.dcs.fmph.uniba.sk/STI2 
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php

---