Please use this identifier to cite or link to this item: http://hdl.handle.net/2445/148597
Title: Coloración del plano: el problema de Hadwiger-Nelson
Author: Barril Pizarro, Sergio
Director/Tutor: Soria de Diego, F. Javier
Keywords: Teoria de grafs
Treballs de fi de grau
Programari
Graph theory
Bachelor's thesis
Computer software
Issue Date: 20-Jun-2019
Abstract: [en] How many colors are needed in order to color the Euclidean plane in a way such that no two points at unit distance have the same color? This problem was first posed by Edward Nelson in 1950, and shortly after the first bounds were found: a lower bound of 4 and an upper bound of 7. These bounds were the best known for almost 70 years, until in April 2018 the biomedical gerontologist Aubrey de Grey shared a graph with 1585 vertices and 7909 edges of length 1, that could not be colored with 4 colors, thus improving the lower bound to 5. Besides looking for graphs with edges of length 1 that can’t be colored with 5 colors (which would further improve the lower bound to 6), one of the current goals is finding a smaller graph that can’t be 4-colored. To that end, two propositional logic tools have proven useful: SAT solvers and DRAT checkers. Currently, the smallest 5-chromatic graph found is due to Marijn Heule, with only 553 vertices. An improvement in both the number of vertices of the smallest 5-chromatic graph and the upper or lower bounds is still being actively pursued.
Note: Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2019, Director: F. Javier Soria de Diego
URI: http://hdl.handle.net/2445/148597
Appears in Collections:Programari - Treballs de l'alumnat
Treballs Finals de Grau (TFG) - Matemàtiques

Files in This Item:
File Description SizeFormat 
codi_font.zipCodi font119.04 kBzipView/Open
memoria.pdf5.38 MBAdobe PDFView/Open
UDGraphs_Windows_v_1.0.zipUDGraphs Windows v. 1.050.79 MBzipView/Open


This item is licensed under a Creative Commons License Creative Commons