Mixed graph coloring
Location: MSRI: Baker Board Room
A mixed graph is a graph with both directed and undirected edges. Mixed graphs come with a (strong) chromatic polynomial and a weak chromatic polynomial; in both cases we count k-colorings (such as with the chromatic polynomial for ordinary graphs) that have to assign different colors to vertices connected by an undirected edge, for directed edges the colors have to obey the > (in the strong case) or >= (in the weak case) relation as we move along the edge. M. Bekc, T. Bogart, and T. Pham proved a reciprocity theorem for strong chromatic polynomials. We will try to come up and prove a reciprocity theorem for weak chromatic polynomials. Furthermore, we will try to use the connection found by H. Furmanczyk, A. Kosowski, B. Ries, and P. Zylinski to obtain a reciprocity theorem for edge coloringsof mixed graphs.
If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.
See more of our Streaming videos on our main VMath Videos page.