DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Entire-choosability of Planar Graphs with Maximum Degree at least 8

Speaker: Dan Cranston, DIMACS

Date: Thursday, October 30, 2008 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We call the vertices, faces, and edges of a plane graph its elements. We call a plane graph entirely k-choosable if, whenever we assign to each element a list of k colors, we can choose a color for each element from its list so that every two elements which are adjacent or incident receive distinct colors.

Wang and Lih conjectured that every plane graph is entirely (D+4)-choosable, where D is the maximum degree of the graph (if true, this is best possible, since K_4 is entirely 7-choosable, but not entirely 6-choosable). They showed that every plane graph with D>11 is entirely (D+4)-choosable and that every plane graph with D>8 is entirely (D+5)-choosable. We improve their results by showing that every plane graph with D>7 is entirely (D+4)-choosable.

We will sketch the proof of our result, but the emphasis will be on our technique, called the discharging method; the discharging method is a bookkeeping technique for simplify counting arguments, and it has most often been used to prove coloring and structural results for sparse graphs. This is joint work with David Lapayowker, of Harvey Mudd College, who was my REU student this summer. We will assume no background material.