Timeline for Local-global approach to graph theory
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 1, 2010 at 9:52 | comment | added | Thomas Bloom | Well, the result mentioned by Gjergji in the question gives some information on the chromatic number if the graph is locally 2-colourable. | |
| Dec 31, 2009 at 21:54 | comment | added | Mariano Suárez-Álvarez | I wonder if there is any kind of local data which gives informatiom about the chromatic number... | |
| Dec 31, 2009 at 19:15 | comment | added | Gjergji Zaimi | Thanks! So basically we can't get information about $\chi(G)$ from neither of the two types of local data. | |
| Dec 31, 2009 at 12:48 | comment | added | Dan Petersen | Similarly, for any k there exists a graph with $\chi(G) > k$ whose girth (length of the shortest cycle) is also greater than k, i.e. the graph G is locally indistinguishable from a tree. This is also due to Erdös. | |
| Dec 31, 2009 at 11:30 | history | answered | Thomas Bloom | CC BY-SA 2.5 |