Nahn Nguyen

Nahn Nguyen

University of Montana
, BH 225

Abstract

Past, Present and Future work on the 123 Conjecture and Variants

Ak-edge-weighting of a graph G is a map w:E(G)→{1,···, k}. Every k-edge-weighting w induces a vertex coloring on G by adding the weight of all the edges at any vertex. In 2004 Karonski, Luczak and Thomason conjectured that for any connected graph G with at least 3 vertices, there exists a 3-edge-weightingthat induces a proper vertex coloring. This conjecture came to be known as the 123 Conjecture. To this day it remains a conjecture; though progress has been made in the form of the 12345 Theorem and other partial results. This talk will focus on variants of the 123 Conjecture including but not limited “total colors” and “twin edge colorings”. Our results on the twin edge coloring problem will be presented along with open problems and directions for future research. This talk is accessible to any undergraduate student with an understanding of modular arithmetic.