Graphs and Matroids Seminar - Kasper Lyngsie

Given a graph G and a set of integers (which we call weights) S ⊂ Z you are asked to find an assignment f : E(G) → S of the weights in S to the edges of G such that the resulting weighted degrees induce a proper vertex-colouring of G. For which G and S can you do this? If it is possible we say that G has the S-property. Clearly K2 does not have the S-property for any set of integers S. The 1,2,3-Conjecture formulated in 2004 by Karonski, Luczak and Thomason states that any graph G with no K₂-components has the {1, 2, 3}-property. In this talk we will briefly go over some of the progress on this conjecture, and then we will turn our attention towards characterising the bipartite graphs without the {1, 2}-property and the bipartite graphs without the {0, 1}-property. The restriction to bipartite graphs is motivated by the fact that deciding whether a given graph has the {1, 2}-property or the {0, 1}-property is an NP-complete problem for general graphs. This is joint work with Jim Geelen.