Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 16.10.2008 at 12:20 in S8, there is the following noon lecture:

Krausz dimension of graphs

Pavel Skums

Belarus State University

Abstract

Krausz k-partition of a graph G is a partition of the set E(G) into cliques (called clusters of a partition) such that every vertex of G belongs to at most k clusters. Minimal natural k such that G has krausz k-covering, is called the krausz dimension of G and denoted by kdim(G).

In my talk I am going to discuss the problem of finding the krausz dimension of graphs as well as estimations for kdim(G) and connections between this parameter and another graph- theoretical parameters. I will focus special attention on the graphs with kdim(G) <= 3. This case is particularly interesting, since it is known that graphs with kdim(G) <= k are exactly intersection graphs of linear k-uniform hypergraphs, and therefore the class of graphs with kdim(G) <= 3 is the direct and natural generalization of the class of line graphs.

References

1. Berge C. Hypergraphs. Combinatorics of Finite Sets. Amsterdam: North-

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010