Tue, April 4, 2017
Public Access Category: All |
||||||||||||||||||||||
|
- Time:
- 11:00am-12:00pm
- Location:
- Ramanujan Hall
- Description:
- Title: Every graph is (2,3)-choosable
Abstract:
A total weighting of a graph G is a mapping f which assigns to each element
z ∈ V (G)∪E(G) a real number f(z) as its weight. The vertex sum of v
with respect
to f is the sum of weight of v and weights of edges adjacent to v. A
total weighting is proper if vertex sums of adjacent vertices are
distinct. A (k, k')-list assignment is a mapping L which assigns to
each
vertex v a set L(v) of k permissible weights, and assigns to each edge
e a set L(e) of k'
permissible weights. We say G is (k, k')-choosable if for any (k,
k')-list assignment L, there is a proper total weighting f of G with
f(z) ∈ L(z) for each z ∈ V (G)∪E(G).
It was conjectured by Wong and Zhu that every graph is (2,
2)-choosable and every
graph with no isolated edge is (1, 3)-choosable. We will see a proof
of the statement in the title, due to Wong and Zhu.