MATH Seminar

Title: Vertex-coloring edge-weightings
Seminar: Combinatorics
Speaker: Michal Karonski of Mathematics and Computer Science, Emory University and Faculty of Mathematics and Computer Science, Adam Mickiewicz University
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2009-10-02 at 4:00PM
Venue: W306
Download Flyer
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, that the vertex weighting induce a proper coloring of the graph.\\ \\ Conjecture [Karonski, Luczak and Thomason, 2001]. Edges of every graph that does not contain a component isomorphic to an edge 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.