Improved Bounds on Coloring of Graphs

Improved Bounds on Coloring of Graphs : This paper by Sokol Ndreca, Aldo Procacci, Benedetto Scoppola (2011) has several improvements on upper bounds of special types of chromatic numbers for graphs, all of them using a recent, improved version of the Lovasz Local Lemma, by Bissacot et al. (2011). We will present the new formulation of the Lemma and the results pertaining to the chromatic numbers for acyclic, star and frugal colouring, relating to the maximum degree of the graph.

Subgraphs of random graphs with specified degrees : If a graph is chosen uniformly at random from all the graphs with a given degree sequence, what can be said about its subgraphs? The same can be asked of bipartite graphs, equivalently 0-1 matrices. These questions have been studied by many people. In my report will provide a partial survey of the field, with emphasis on two general techniques: the method of switchings and the multidimensional saddle-point method.

Event Topic

Discrete Applied Math Seminar