On Total Equitable Choosability

This talk will be accessible to those with knowledge of basic graph theory. The concept of equitable coloring was formally introduced by Meyer in 1973. An equitable \(k\)-coloring of a graph \(G\) is a proper \(k\)-coloring of \(G\) such that the sizes of the color classes differ by at most one. Equitable colorings are useful in applications where one needs to do conflict-free allocation of resources without using any particular resource excessively often. Consider a graph where vertices represent courses to be offered at a University and edges are placed between courses which cannot run at the same time. Then, one seeks a proper vertex coloring of the graph where colors are available time slots. It is clearly preferable to not use any particular time slot excessively often due to constraints like: number of classrooms available, number of professors available, etc.

In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring, called equitable choosability, which is applicable when there is only a certain list of colors available at each vertex in the graph. In this talk, Mudrock studies and presents results on the equitable choosability of total graphs, that is color both vertices and edges simultaneously. No knowledge of list coloring or total graphs will be assumed.

Event Topic

Discrete Applied Math Seminar