Melissa Fuentes (Binghamton)

Proper Connection of Graphs

Abstract for the Combinatorics Seminar
2014 February 18

Proper edge colorings of graphs have been a popular topic in graph theory since the work of Vizing on the chromatic index (edge chromatic number). While the study of proper edge colorings of entire graphs was the topic of interest when the subject began decades ago, more recent works have focused on finding properly colored subgraphs.

The types of properly colored subgraph that I will be most concerned with in this talk are paths. My main focus will be on graphs which are l-properly connected, that is, graphs whose vertex pairs are connected by l pairwise internally disjoint properly edge colored paths. I will discuss the proper connection number of a graph G, Pcl(G), a graph parameter which provides the smallest number of colors needed in order to make a graph G l-properly connected. In particular, I will describe a conjecture made in 2011 by Borozan et al. concerning 2l-connected bipartite graphs. I will look at the proper connection number of a type of bipartite graph called a circulant graph. As well as being a result in itself, this yields progress on a conjecture of Borozan et al.

Time permitting, I will also discuss another conjecture by Borozan et al., which I have recently become very interested in.


To the Combinatorics Seminar Web page.