Colloquium by Petr Gregor (Charles University, Prague): Incidence colorings of subquartic graphs and Cartesian products
Two incidences (u,e) and (v,f) of vertices u, v and edges e, f (respectively) are adjacent if u=v, or e=f, or uv is one of edges e, f. An incidence coloring of a graph G is a coloring of its incidences such that adjacent incidences have distinct colors. We show that every graph of maximal degree 4 has an incidence coloring with 7 colors. Furthermore, we present sufficient conditions for Cartesian product graphs to have incidence colorings with Delta+2 colors where Delta is the maximal degree. In particular, we confirm a conjecture of Pai et al. on incidence colorings of hypercubes. Joint work with B. Lužar and R. Soták.
Time & Location
Dec 03, 2018 | 04:00 PM s.t.
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)