Seminár z teoretickej informatiky - Róbert Lukoťka

v piatok 11.5.2018 o 11:00 hod. v miestnosti M/213

09. 05. 2018 08.52 hod.
Od: Rastislav Královič

Prednášajúci: Róbert Lukoťka

Názov: Deciding 3-edge-colourability of graphs

Termín: 11.5.2018, 11:00 hod., M/213

Abstrakt:
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