Bojan Mohar: Is there a structural graph theory based on the spectral radius?
Datum objave: 14. 4. 2009
Seminar za teorijo grafov in algoritme
Četrtek 16. 4. 2009 ob 12:15 v predavalnici 3.07 na Jadranski 21.
Every tree of maximum degree $D$ is a subgraph of the infinite
$D$-regular tree. This observation immediately implies that the spectral
radius of every such tree
is at most $2\sqrt{D-1}$. One can also show (T. Hayes, V. Nikiforov,
Z. Dvo\v rak and B. Mohar) that planar graphs and graphs of bounded
genus satisfy a similar relation: the spectral radius is
$O(D^{1/2})$.
Whenever a result can be proved for tree-like graphs and for graphs of
bounded genus, it is natural to ask if it can be extended to a more
general setting of minor-closed families (or beyond) and what new tools
does it bring. In the talk we will try to answer this question.