Summer reads 1: Colorings, traveling salesmen, and central nodes in networks

As every summer, we have collected some of our articles to help you choose your summer reads! Have a look at our articles on colorings, the traveling salesman problem, and centrality. Enjoy!

Coloring infinitely many points

Graph theory is a very vibrant and modern topic in mathematics. Many problems related to graphs look more like puzzles, and you often don't need prerequisite knowledge to start working on them. You can also make drawings of graphs to come up with ideas and answers. 

At the same time, in graph theory, many results are seemingly simple to state, but proving them rigorously demands a lot of work. You can start by reading a personal story from teaching. If you want to go deeper into the topic of graph colorings, you can have a look at the two articles written by Leonidas Theocharous. One introductory on graph colorings and their importance in graph theory, and the second on the coloring number of the plane graph. This is an infinite graph whose coloring number is still nowadays unknown, the only thing we know is that it is equal to 5, 6, or 7!

De Grey's 1581-vertex construction, picture taken from this article on Quantamagazine.

A traveler trying to visit them all

Suppose you are running a delivery service. You have a single truck and each day you must deliver a large number of parcels to various cities throughout the country. Then you face the following problem: in which order should you visit the cities? In other words, you want to find a round-trip that starts at the depot where the parcels are kept, then visits each of the given cities, and finally returns to the depot. Such a round-trip is called a tour of the given cities. Of course, the goal is to find a tour with minimum travel cost. Here, travel cost can refer to the average time it takes to follow the tour or the total length of the tour. Computer scientists call this problem the Travelling Salesman Problem, or TSP for short. You may think that if we know the cities to be visited and the travel costs of the roads connecting them, then a computer can easily compute a shortest tour. But the fact that TSP is so simple to state is deceptive: it turns out finding the best tour is extremely difficult, even with state-of-the-art computers. Want to know why? Read this article. Thankfully many smart algorithms exist when considering practical situations. In his article Roshan Mayes discusses his research on TSP and how creative ideas can make TSP more manageable!

The optimal biking route in the Netherlands visiting 57.912 national monuments.

How do you decide who is the most important?

In the past year, we published various articles about identifying important nodes in a network. To do this we have to give a mathematical meaning to the words "important". This was the goal of the first article on this topic written by Anne van Grinsven. Anne also discusses how a mathematical concept called an eigenvalue plays an important role in identifying central nodes in a network. In a second article, Nandan Malhorta discusses another aspect of networks related to eigenvalues. Namely, how eigenvalues can help find a random walker on a network. In a third article, Manish Pandey gives an overview of methods on how to measure which nodes are central. Below can also find an interactive animation to experiment on your own with various centrality measures. Try out on your own and try to understand how different measures relate to each other.

Relax with a nice animation or video

Would you prefer to watch some videos and illustrations? If you visit the homepage of the Network Pages you may get the impression that we focus entirely on communicating mathematics through writing articles. But there is much more! We invest a lot of time in developing other means of communicating mathematical results as well.

On the Network Pages, you can also find, for example, science illustrations and videos. Additional to these, we also invest time and energy into exploring the opportunities that animations and simulations offer! Have a look at our updated website with a complete list of the animations we have developed until now. These animations were developed by Robert Fitzner and Martijn Gösgens from the Eindhoven University of Technology. Feel free to use them for educational and scientific purposes! We would like to ask you though to mention the Network Pages and link to the website whenever you use an animation. If you have suggestions or wishes for specific animations or simulations, you can contact us at

And when you will be resting from all the summer activities you can watch this beautiful video developed by four students of the University of Amsterdam, Samuel Asmeron, Thomas de Boer, Anna Heikamp, and Daan Hoogcarspel.

Would you like to stay up to date whenever a new post appears on the Network Pages? Then subscribe to our mailing list, follow us on Twitter or on LinkedIn.

Comments are closed