On 23.07.2009 at 12:20 in S8, there is the following noon lecture:
Some defective parameters in graph theory
University of Alaska Fairbanks
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010