Probabilistic methods and coloring problems in graphs
Guillem Perarnau · 2010
Aquest projecte esta dedicat a estudiar el k-essim nombre cromatic generalitzat que sorgeix de les descomposicions Low Tree--Depth en grafs usant metodes probabilistics.. Una extensio natural del nombre cromatic d'un graf es l'estudi de particions de grafs en les que cada i parts indueixen un subgraf amb un cert parametre acotat en funcio de i, per exemple cada i parts tenen com a molt i-1 arestes. En particular el nombre cromatic generalitzat es le minim nombre de parts per tal que cada i parts te 'treedepth' com a molt i. Resultats recents proven que grans classes de grafs tenen parametres d'aquest tipus acotats. L'objectiu del projecte es (i) fer servie metodes probabilistics per donar cotas ajustades d'aquests parametres i (ii) estudiar el seu valor per grafs aleatoris.