My dad loved maths. He was an engineer, but as a kid he loved mathematics. Probably he said enough things to get me interested.

I grew up in a home where mathematics was treated with utmost respect ...

... had passion and enthusiasm for mathematics, and made us, the students, believe that what we were learning in that class was the most interesting thing in the world.

... at the end of 6th grade we had to take a very serious exam to be allowed to go into a maths 7th grade which I did, and I passed it. And I remember it was the first sort of serious exam I had ever taken in my life. It was three hours and I was 12 years old, and I remember walking out of this exam just thinking "I have not been so tired ever in my life." I just didn't think it was possible for a human being to be so tired.

I lived in Haifa, and a friend from school told me that on Thursday afternoons one could go to the Technion and take this informal class run by mathematics graduate students. It was an absolutely amazing experience! Sometimes we would think about problems, other times the teachers would tell us a simplified version of a lecture that they themselves had heard a few days earlier. Again, we all felt that nothing out there could even compare to what we were doing. That was when I decided that I would major in maths in college.

If six people come to a party, then either there are three who know each other or three who do not. Five are not enough. I heard this problem when I was about 14 or 15; and I have never been the same person again.

Because I grew up in Israel, I had to serve in the army. So, my first day in the army, I went up to my boss, I said, "I would like to take courses at the university, so is it okay if on Thursdays I come late and stay late?" And I think he was just so shocked, he said "Okay". Later it turned out that in fact you could do that but only if you had been there for a couple of years. But luckily I didn't check the rules.

I showed up at Princeton, and I knew I wanted to work with Paul Seymour. The Strong Perfect Graph Conjecture was the problem he was interested in the time. I was lucky at the time that I didn't understand what was appropriate and what wasn't. I came up to him and said "Can I work with you on this?" He said "sure." When he saw I was contributing, I became part of the group. I don't know if when I first approached him he thought it was a little bit strange.

A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs is important for several reasons. For instance, many problems of interest in practice but intractable in general can be solved efficiently when restricted to the class of perfect graphs. Also, the question of when a certain class of linear programs always have an integer solution can be answered in terms of perfection of an associated graph.

In the first part of the paper we survey the main aspects of perfect graphs and their relevance. In the second part we outline our recent proof of the Strong Perfect Graph Conjecture of Berge from 1961, the following: a graph is perfect if and only if it has no induced subgraph isomorphic to an odd cycle of length at least five, or the complement of such an odd cycle.

A trigraph T is a complete graph with the edge set partitioned into three sets: strong edges, strong non-edges and switchable edges. A trigraph is Berge if for every subset S of switchable edges the graph G whose edge set is the union of S with the set of all strong edges of T is Berge.

We prove the following result for Berge trigraphs:

The decomposition result of M Chudnovsky, N Robertson, P Seymour and R Thomas, 'Progress on perfect graphs' for Berge graphs extends (with slight modifications) to trigraphs i.e. either T belongs to one of a few basic classes or T has a decomposition, where all the "important" edges and non-edges in the decomposition are strong edges and strong non-edges of T respectively.

In the proof of the Strong Perfect Graph Theorem we used three kinds of decompositions: skew-partitions, 2-joins and M-joins. The result about Berge trigraphs implies that the M-join decomposition is in fact unnecessary.

Another consequence of the result about Berge trigraphs is the following: if G is a Berge graph then either it belongs to one of a few basic classes, or it admits a skew partition or an M-join, or it admits a 2-join so that neither half of it is just an induced path, or the complement of G admits a 2-join.

I would like to thank my advisor, Paul Seymour, for his help and guidance, and for teaching me more that I thought I could possibly ever learn. I would also like to thank my parents - for their immense support and for never mentioning the phone bills. Special thanks go to my friends, in Princeton and all over the world - thank you for listening. And last but not least, I would like to extend my thanks to our graduate coordinator Jill Le Clair - thank you so much for your patience.

Young mathematicians are called 'promising' if they are expected to become at least half as good in 10 years as Maria is now.

Claude Berge introduced the class of perfect graphs in 1960, together with a possible characterisation in terms of forbidden subgraphs. The resolution of Berge's strong perfect graph conjecture quickly became one of the most sought-after goals in graph theory. The pursuit of the conjecture brought together four important elements: vertex colourings, stable sets, cliques, and clique covers. Moreover, D R Fulkerson established connections between perfect graphs and integer programming through his theory of antiblocking polyhedra. A graph is called perfect if for every induced subgraph H the clique-covering number of H is equal to the cardinality of its largest stable set. The strong perfect graph conjecture states that a graph is perfect if and only if neither it nor its complement contains, as an induced subgraph, an odd circuit having at least five edges. The elegance and simplicity of this possible characterisation led to a great body of work in the literature, culminating in the proof by Chudnovsky, Robertson, Seymour, and Thomas, which was announced in May 2002, just one month before Berge passed away. The long, difficult, and creative proof by Chudnovsky and her colleagues is one of the great achievements in discrete mathematics.

When Daniel Panner and Maria Chudnovsky married two years ago, he moved to her two-bedroom co-op in Morningside Heights from his studio condominium in the Ansonia on the Upper West Side. She was eager to move again. "I was thinking, now that there's two of us, we should probably upgrade our living situation," she said. "I felt, if I alone could afford that place, we could as a couple afford a bigger place." Besides, they were planning for a baby. ... The Upper West Side was ideal for them. Mr Panner, 45, a viola player, teaches at Mannes College and the Juilliard School, while Dr Chudnovsky 36, a mathematician who specialises in graph theory, is a professor at Columbia University.

Maria Chudnovsky, 35, New York. Mathematician at Columbia University whose work is deepening the connections between graph theory and other major branches of mathematics, such as linear programming and geometry.

Chudnovsky says that when she does research her approach is different for every problem. A common technique is to find one small case to play with and see if it can give her any clues about the larger question. She says that the fellowship, which comes with $500,000 over the course of five years, no strings attached, won't change the type of research she does, but that it gives her the freedom to attack problems that seemed too risky before. "Now I'll try them. The biggest advantage of the fellowship is that if I work on something for a year and fail, people won't say, 'she's no good.'"

Since graph-colouring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Results of Kamínski and Lozin, Holyer, and Levin and Galil imply that the problem remains NP-complete, unless H is the disjoint union of paths. Recently, the question of colouring graphs that do not contain certain induced paths has received considerable attention. Only one case of that problem remains open for k-colouring when k ≥ 4, and that is the case of 4-colouring graphs with no induced 6-vertex path. However, little is known for 3-colouring. In this paper we survey known results on the topic, and discuss recent developments.

Chudnovsky has been exploring another question about perfect graphs. Can you efficiently colour the dots with the smallest possible number of colours? The answer to this question is yes, but all the known algorithms use a complex technique known as combinatorial optimisation. Might there be another technique that relies solely on graph theory? Recently, Chudnovsky and Columbia graduate student Irene Lo, with Frédéric Maffray at the Grenoble Institute of Technology, Nicolas Trotignon of École Normale Supérieure de Lyon, and Kristina Vuškovic of the University of Leeds, were able to make progress on this, designing such an algorithm for a large subclass of perfect graphs.