- This event has passed.

# CO seminar – Gabriel Coutinho

## February 2 @ 12:30 - 13:30

**Location:** MF 12

**Speaker: **Gabriel Coutinho (Universidade Federal de Minas Gerais)

**Title: **Spectral upper bounds to the Grundy number of a graph

**Abstract:
**The Grundy number is the minimum number of colors needed to properly color graph using the first-fit greedy algorithm regardless of the vertex ordering. It is NP-Hard to compute, it is also naturally lower bounded by the chromatic number, but it is still trivially upper bounded by the maximum degree plus one. However, the well-known spectral upper bound to the chromatic number due to Wilf, which replaces the maximum degree by the largest eigenvalue, does not hold for the Grundy number.

This motivated our pursuit for a non-trivial spectral upper bound to the Grundy number. In this journey we ended up using the path-tree, a construction due to Godsil and Gutman which connects the matching polynomial and the characteristic polynomial of the graph. This talk will explain this connection and also survey other results in this topic. This is joint work with Thiago Assis and Emanuel Juliano.