# Parties, doughnuts and colouring: welcome to the world of graph theory

## Ahead of her Hamilton Lecture in Dublin on October 16th, Prof Maria Chudnovsky of Princeton University connects the dots between the abstract and the real

Prof Maria Chudnovsky: ‘Maths is beautiful and a great field to pursue.’

Maria you are giving the annual Hamilton Lecture soon in Dublin, what will you talk about?

I will talk about simple problems or puzzles that relate to parties, doughnuts and colouring and explain how they grow into research directions in graph theory, and what kinds of problems researchers in graph theory work on today.

What do you mean by graph theory?

The graphs I talk about are not the ones with X and Y axes. In the field of graph theory, a graph is an abstract concept. Very simply, if you put some dots on a piece of paper and then connect some of the pairs of dots with lines, then you have a graph. It maps relationships between objects.

In your PhD at Princeton, you were part of a group that solved a big problem in graph theory. What was that?

In 1961, the French mathematician Claude Berge defined the notion of “perfect graphs” that behave particularly well with respect to a basic notion in graph theory called “colouring”. In 2003, four of us were able to prove a theorem that says a graph is perfect if and only if it doesn’t contain certain structural faults, thus verifying a conjecture that Berge made more than 40 years earlier.

And what are you researching now?

I work in a field called “structural graph theory”, where you start with a property and you want to understand the structure of all graphs that have this property. My doctoral thesis work was one example of this, but there are many more questions to ask there.