To access the full text documents, please follow this link: http://hdl.handle.net/2099.1/10240

Probabilistic methods and coloring problems in graphs
Perarnau Llobet, Guillem
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Serra Albó, Oriol
Aquest projecte està dedicat a estudiar el k-èssim nombre cromàtic generalitzat que sorgeix de les descomposicions Low Tree--Depth en grafs usant mètodes probabilístics.. Una extensió natural del nombre cromàtic d'un graf és l'estudi de particions de grafs en les que cada i parts indueixen un subgraf amb un cert paràmetre acotat en funció de i, per exemple cada i parts tenen com a molt i-1 arestes. En particular el nombre cromàtic generalitzat és le mínim nombre de parts per tal que cada i parts té 'treedepth' com a molt i. Resultats recents proven que grans classes de grafs tenen paràmetres d'aquest tipus acotats. L'objectiu del projecte és (i) fer servie mètodes probabilístics per donar cotas ajustades d'aquests paràmetres i (ii) estudiar el seu valor per grafs aleatoris.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria
Combinatorial analysis
Graph coloring
Probabilistic method
Combinacions (Matemàtica)
Classificació AMS::05 Combinatorics::05D Extremal combinatorics
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/masterThesis
Universitat Politècnica de Catalunya
         

Show full item record

Related documents

Other documents of the same author

Perarnau Llobet, Guillem; Serra Albó, Oriol
Abiad, Aida; Fiol Mora, Miquel Àngel; Haemers, Willem H.; Perarnau Llobet, Guillem
Perarnau Llobet, Guillem; Petridis, Georgios
Muntés Mulero, Víctor; Padrol Sureda, Arnau; Perarnau Llobet, Guillem; Pfeifle, Julián
Padrol Sureda, Arnau; Perarnau Llobet, Guillem; Pfeifle, Julián; Muntés Mulero, Víctor
 

Coordination

 

Supporters