Document Type
Lecture
Publication Date
11-20-2009
Abstract
A weighting of the edges of a graph with integer weights gives rise to a weighting of the vertices, the weight of a vertex being the sum of the weights of its incident edges. It is natural to consider edge weighting where we require that adjacent vertices have different weights that is, the vertex weighting induce a proper coloring of the graph. Conjecture (Karo'nski, Luczak and Thomason, 2001) Edges of every graph that does not contain a component isomorphic to K2 can be weighted with the integers {1, 2, 3} such that the resultant vertex weighting is a proper coloring. In my talk I will discuss some recent developments regarding the above conjecture. In particular, I will present a joint result, with Maciej Kalkowski and Florian Pfender, showing that {1, 2,..., 5-edgeweighting suffices to properly color vertices of a graph.
Relational Format
presentation
Recommended Citation
Karonski, Michal, "On the 1-2-3-conjecture" (2009). Colloquium. 44.
https://egrove.olemiss.edu/math_colloquium/44
