Skip to Content

Alexa Serrato

Thesis

Reed's Conjecture and Cycle-Power Graphs

Advisor
Nicholas J. Pippenger
Second Reader(s)
Mohamed Omar

Abstract

Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.

Proposal

Proving Reed's Conjecture for Certain Classes of Graphs

Additional Materials

Poster