I have just finished a first course in graph theory and finished my undergraduate degree in mathematics. I have two broad questions about research/further study in graph theory.
- What is the natural next step to studying graph theory: I would appreciate any book recommendations for a second course in graph theory. Are there any classic or very important/ impactful papers related tothe field that I should read?
- How does the future of graph theory research look? Are there good mathematically based problems left? Has the field been dominated by the study of graph algorithms? Are graph algorithms very interesting on their own i.e would someone who studied pure math in undergrad find enjoy the problems in this area/ would the be able to understand the problems in this area with no CS background?
Thanks !
I did a PhD in graph theory a bit more than a decade ago. As far as what I did to progress from an undergraduate to publishing an original result for my thesis which answered a question that was open at the time, I took a course in graph theory and a course in graph algorithms between my last two years of undergrad and my first couple of years in graduate school, and then I started working on problems/research directions. I personally found it was less about having a huge base of knowledge, and more about picking a good problem to work on and just being good at figuring out the problem.
Most importantly in my opinion, I would suggest textbooks that have the best selections of exercises/problems--graded from easy to moderate to quite challenging, to unsolved. A terrific example in that regard is Tom Leighton's book Introduction To Parallel Algorithms and Architectures. I went through the book and worked through many of the exercises in that book, it was extremely helpful for me. Also, google Laszlo Lovasz. He has several texts each one in a different research direction. I think the level is quite appropriate for someone who wants to go into research.
Then for graduate school I would look for an advisor whose research interests sound the most appealing to you--after you have done some searching and studying on your own that is.
As for the rest of the questions you asked, the best way I know to answer is that you have to do some searching yourself (sorry). I am not in academia anymore and even besides that, the field had long since broadened to the point where no one person can know that much about even an $\epsilon$-fraction of the research directions anyway. A look through the pure math--discrete math--theoretical computer science journals past and present may also be quite helpful.