Das Friday Seminar ist ein informelles wöchentliches Seminar für

• die Mitglieder der Arbeitsgruppe Diskrete Mathematik
• die Studenten der Arbeitsgruppe
• jeden der sonst interessiert ist

Jede Woche wird ein Vortrag gehalten der folgender Art:

• Präsentation der eigenen Forschung
• Vorstellung eines offenen Problems dass der/die Vortragende momentan bearbeitet
• Präsentation des geplanten Vorhabens für eine Bachelor-, Master-, Diplom- oder Doktorarbeit
• Präsentation der Resultate einer Bachelor-, Master-, Diplom- oder Doktorarbeit
• Vorstellung eines Forschungsartikels welcher für die Arbeitsgruppe von Interesse sein könnte

Das Seminar findet im Seminarraum 3.068 im Kollegiengebäude Mathematik 20.30 statt.

NÄCHSTER VORTRAG

Freitag 15. März, 14:00
Raum 2.066

Daniel Goncalves

Entropy Compression Method Applied to Graph Coloring

The celebrated Lovasz Local Lemma (LLL) is a probabilistic tool with many applications, particularly in graph coloring. The Entropy Compression Method (ECM) was introduced by Moser and Tardos in 2009 as an algorithmic version of the LLL. Many of the results previously obtained by LLL were recently slightly improved using ECM. Moreover ECM seems to be easier than LLL to handle: some of the results obtained using ECM, could have been obtained earlier with LLL.

Here we propose a general framework for graph coloring problems based on ECM. This framework is similar to the one of Esperet and Parreau, but it yields to tighter bounds. In particular, we derive that every graph with maximum degree has an acyclic vertex-coloring using at most colors, and a non-repetitive vertex-coloring using at most colors.

This is joint work with M. Montassier and A. Pinlou.

Vortragsübersicht

• 2016/02/12 -- Jonathan Rollin -- Conflicts in Ordered Graphs

• 2016/02/05 -- Torsten Ueckerdt -- Blossoming Trees and Planar Graphs
• 2016/01/29 -- Yassine Marrakchi -- Approximation Scheme for Maximum Independent Set of Rectangles
• 2016/01/22 -- Maria Axenovich -- Transversal Families for Edge-colored Complete Graphs
• 2016/01/15 -- Gregor Lagodzinski -- Combinatorics of 2-connected Series-parallel Graphs
• 2015/12/18 -- Torsten Ueckerdt -- Schnyder's Theorem -- continued

• 2015/12/11 -- Fabian Stroh -- Sharing Even Spiders
• 2015/12/04 -- Jonathan Rollin -- Ramsey Multiplicities
• 2015/11/27 -- Torsten Ueckerdt -- The Interval Number of Planar Graphs
• 2015/11/20 -- Annette Karrer -- Uncolorable Bihypergraphs with Few Edges
• 2015/11/13 -- Julia Heller -- Noncrossing Partitions in Geometric Group Theory

• 2015/11/06 -- Jonathan Rollin -- The Chromatic Number of Ordered Graphs
• 2015/10/30 -- Kolja Knauer -- Drawing Graphs with Vertices and Edges in Convex Position
• 2015/10/23 -- Torsten Ueckerdt -- Schnyder's Theorem
• 2015/09/11 -- Mujiangshan Wang -- The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM∗ Model
• 2015/07/17 -- Maria Axenovich -- Report from Ron Graham's Birthday Conference

• 2015/07/10 -- Stefan Walzer -- Finding Monochromatic Cubes in Coloured Cubes
• 2015/07/03 -- Jonathan Rollin -- Degrees and Factors in Graphs
• 2015/06/26 -- Stefan Walzer -- Secure Card-Based Computation
• 2015/06/19 -- Jonathan Klawitter -- Crossing Minimisation in Book Embeddings
• 2015/06/12 -- Stephen G. Kobourov -- 1-Planar Graphs

• 2015/06/05 -- Maria Axenovich -- Hales-Jewett Theorem and Ramsey Classes
• 2015/05/29 -- Peter Stumpf -- On Covering Numbers of Different Kinds
• 2015/05/22 -- Sebastian Ziesche -- A Short Introduction to Percolation
• 2015/05/15 -- Torsten Ueckerdt -- The Etiquette of Sharing a Cake
• 2015/05/08 -- Alexander Koch und Stefan Walzer -- TikZ vs. Ipe

• 2015/04/24 -- Felix Joos -- An Approximation of the Packing-Covering Duality
• 2015/04/17 -- Torsten Ueckerdt -- Combinatorial Graph Sharing Games
• 2015/02/06 -- Stefan Walzer -- 2-Dimension and Ramsey Lattices
• 2015/01/30 -- Maria Axenovich -- Size Anti-Ramsey Numbers
• 2015/01/23 -- Jonathan Rollin -- Ramsey Equivalent Graphs

• 2015/01/16 -- Torsten Ueckerdt -- Contact Representations of Sparse Planar Graphs
• 2015/01/09 -- Dirk Tröndle -- Convex Distance Function Delaunay Triangulations
• 2014/12/19 -- Valentin Braun -- On-line Graph Colorings
• 2014/12/12 -- Anika Kaufmann -- On Clumsy Packing of Complete Graphs
• 2014/12/05 -- Jennifer Weidelich -- Adjacent Vertex Distinguishing Colorings of Bipartite Graphs

• 2014/11/28 -- Pascal Weiner -- H-free Colourings of Planar Graphs
• 2014/11/21 -- Stefan Walzer -- On the Size of Sumsets
• 2014/11/14 -- Jonathan Klawitter -- Transforming Rectangles Into Squares
• 2014/10/31 -- Jonathan Rollin -- Brooks Type Results for Conflict-Free Colorings and -Factors
• 2014/10/24 -- Torsten Ueckerdt -- Online Coloring Between Two Lines (Folien)

• 2014/07/25 -- Kunal Dutta -- On the Discrepancy of Certain Point-Capturing Hypergraphs
• 2014/07/18 -- Jonathan Rollin -- Conflict-Free Colorings and Factors of Regular Graphs
• 2014/07/11 -- Georg Osang -- The Local Chromatic Number
• 2014/07/04 -- Andre Kündgen -- Spanning Quadrangulations of Triangulated Surfaces
• 2014/06/27 -- Sarah Lutteropp -- On Layered Drawings of Planar Graphs

• 2014/06/13 -- Jennifer Weidelich -- Adjacent Vertex Distinguishing Colorings
• 2014/06/06 -- Jonathan Klawitter -- Transforming Rectangles Into Squares
• 2014/05/30 -- Stefan Walzer -- Disjoint Induced Subgraphs of the Same Order and Size
• 2014/05/23 -- Pascal Weiner -- Improper Colourings of Graphs
• 2014/05/16 -- Open Discussion -- Sympossium Diskrete Mathematik 2014

• 2014/05/02 -- Peter Stumpf -- Covering Numbers of Different Kinds
• 2014/04/25 -- Anika Kaufmann -- Clumsy Packings of Regular Graphs Into a Complete Graph
• 2014/04/11 -- Piotr Micek -- Lower Bounds for On-Line Graph Colorings
• 2014/02/13 -- Yury Person -- Powers of Hamilton Cycles in Pseudorandom Graphs
• 2014/02/07 -- Sarah Lutteropp -- On Layered Drawings of Planar Graphs

• 2014/01/31 -- Stefan Walzer -- Tron : A Two Player Game on Graphs
• 2014/01/24 -- Annette Karrer -- Simultaneous Embeddings of Outerplanar Graphs
• 2014/01/17 -- Torsten Ueckerdt -- The Density of Fan-Planar Graphs
• 2014/01/10 -- Maria Axenovich -- On Distinguishing Colorings
• 2013/12/20 -- Dirk Tröndle -- Convex Distance Funtion Delaunay Triangulations

• 2013/12/13 -- Fabian Stroh -- Coloring Graphs Using Topological Lemmas
• 2013/12/06 -- Enrica Cherubini -- Coloring Mixed Hypergraphs
• 2013/11/29 -- Jonathan Rollin -- Hamiltonicity in Sparse Graphs With High Chromatic Number
• 2013/11/18 -- Torsten Ueckerdt -- Scattered Sets in Cocomparability Graphs
• 2013/07/19 -- André Kündgen -- Central digraphs

• 2013/02/12 -- Maria Axenovich -- On Ramsey Numbers and Size Ramsey Numbers
• 2013/02/05 -- Torsten Ueckerdt and Maria Axenovich -- Non-crossing Connectors in the Plane and Twins
• 2013/01/29 -- Maria Axenovich -- On a Reconstruction Problem for Sequences
• 2013/01/22 -- Torsten Ueckerdt -- Combinatorial and Geometric Properties of Planar Laman Graphs
• 2013/01/15 -- Jonathan Rollin -- Unique Edge Colorings

• 2012/12/18 -- Fabian Stroh -- Coloring Kneser Graphs
• 2012/12/11 -- Ignaz Rutter -- Research on Stack- and Queue-number of Graphs
• 2012/12/04 -- Torsten Ueckerdt -- Research on Coloring Geometric Hypergraphs
• 2012/11/27 -- Alexander Koch -- Representations of Graphs by Outside Obstacles
• 2012/11/20 -- Daniel Hoske -- Book Embedding with Fixed Page Assignments

• 2012/11/13 -- Maria Axenovich -- On bar-visibility representations of graphs
• 2012/11/06 -- Judith Stumpp -- Online Size Anti-Ramsey Numbers
• 2012/10/30 -- Stefan Walzer -- Clumsy Packings - Wasting Space in Geometric Puzzles
• 2012/10/23 -- Jonathan Rollin -- Report from 4 PCC, Poznan
• 2012/10/16 -- Torsten Ueckerdt -- The Twin Problem