Projects per year
Abstract
Treewidth is an important and wellknown graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n, k) is the graph with vertex set (^{[n]}_{k}), such that two vertices are adjacent if they are disjoint. We determine, for large values of n with respect to k, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdo{double acute}sKoRado Theorem (for large n with respect to k) when a number of disjoint pairs of ksets are allowed.
Original language  English 

Article number  P1.48 
Pages (fromto)  1  11 
Number of pages  11 
Journal  The Electronic Journal of Combinatorics 
Volume  21 
Issue number  1 
Publication status  Published  28 Feb 2014 
Keywords
 Erdo{double acute}sKoRado
 Graph theory
 Kneser graph
 Separators
 Treewidth
Projects
 3 Finished

Graph colouring via entropy compression
Australian Research Council (ARC)
2/01/14 → 31/12/17
Project: Research

Hadwiger's graph colouring conjecture
Wood, D. & Zhou, S.
Australian Research Council (ARC), University of Melbourne
1/01/12 → 30/04/15
Project: Research

The Structure and Geometry of Graphs
Australian Research Council (ARC)
1/01/08 → 31/12/13
Project: Research