Department of
Applied
Mathematics

Some defective parameters in graph theory

John Gimbel

University of Alaska Fairbanks

Abstract

Many of the most studied topics in graph theory can be defined in terms of independent sets. The notion is extended in the following way: for a given integer k, let us say a set of vertices is k-sparse if it induces a graph with maximum degree at most k. So, for example, we can expand the notion of coloring. The k-defective chromatic number is the fewest number of colors we need to color vertices so that each color class is k-sparse. Likewise, we can extend the notion of ramsey numbers, looking for large k-sparse sets in a graph or its compliment. We will discuss these and some related topics.