The edge-coloring game on some trees with maximum degree four and adjacent degree-four vertices

18. Juni 2018

Vortragsreihe: Mathematisches Kolloquium

17:00 Uhr (bis 18.00 Uhr)

FernUniversität, Gebäude 3, 4. Stock, Seminarraum E08, Universitätsstr. 11, 58097 Hagen

Dr. Dominique Andres, Lehrgebiet Diskrete Mathematik und Optimierung

Wai Lam Fong
The Education University of Hong Kong

Auskunft erteilt
Dr. Dominique Andres

In diesem mathematischen Vortrag werden Grundkonzepte der Theorie der Kantenfärbungspiele eingeführt und dann speziell Kantenfärbungsspiele auf bestimmten Arten von Wäldern untersucht.

Der Vortrag ist auf Englisch.

In an edge-coloring game, two players, Alice and Bob, alternatively choose a color from a given set of colors to color an uncolored edge of an initially uncolored finite graph G such that no adjacent edges receive the same color. Alice wins the game if all edges of G are finally colored; otherwise, Alice loses. The parameter game chromatic index Xg'(G) of G is the least number of colors in the set so that Alice has a winning strategy for the game. It is known that if the maximum degree D(T) of a tree T is not 4, Xg'(T)<=D(T)+1. If D(T)=4 and T doesn’t contain adjacent 4-vertices (degree-4 vertices), the inequality still holds. In this talk, we show that it is still valid if every 4-vertex has at most one neighbor of degree 4.

This is joint work with Wai Hong Chan and Ge Nong.

Gerd Dapprich | 20.09.2018