Speaker: Dan Ullman, George Washington University

Title: A Whirlwind Tour of Fractional Graph Theory

Abstract: It is relatively easy to prove the Five Color Theorem but notoriously difficult to prove the Four Color Theorem. So what about the Four-and-a-Half Color Theorem? Easy or hard? What does the question even mean? Fractional Graph Theory is the study of such graph theory parameters as chromatic number, matching number, covering number, domination number, and so forth, but replacing the word "set" in the usual definition with the two words "fuzzy set". This process of "fractionalizing" graph parameters can also be thought of as the process of relaxing integer programs into linear programs. We'll sample an assortment of results about the fractional chromatic number, the fractional matching number, the fractional arboricity, and a few other fractional graph parameters.

Place: Science and Technology Building I, Room 242

Refreshments will be served before the talk at 3:00 p.m. in Room 222.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491