We use cookies on this site to enhance your experience.
By selecting “Accept” and continuing to use this website, you consent to the use of cookies.
I received my masters and PhD in Combinatorics and Optimization at the University of Waterloo following a BSc (Honours) in Mathematics at the University of Regina.
I have taught graduate courses at Stanford University, Cornell University, Université Pierre et Marie Curie (Paris 6), University of Waterloo, and here at 51本色. I have made extended research visits in France, Denmark, China, and the U.K.
My research is in graph theory and algorithms.
A vast number of fundamental problems on graphs, such as graph colouring, are NP-complete. This is believed to mean that efficient (that is, polynomial-time) algorithms can not be found for all instances. Often graphs arising in applications have special structure which can be analyzed and exploited to design efficient algorithms on these graphs for problems which are NP-complete in general.
Another main area of my research is on parity theorems. Often parity theorems are proved by counting arguments. Another approach, introduced by Andrew Thomason, is to construct a graph, which we call an exchange graph, in which the odd-degree vertices correspond precisely to the objects one wants to show there are an even number of. Christos Papadimitriou calls this approach the polynomial parity argument (PPA). It provides an algorithm for given one of the objects, finding another, by walking in the exchange graph from one odd-degree vertex to another. A main question is: what is the complexity of such algorithms? Exchange graphs are generally very large compared to the input problem.
My current projects include parity theorems about paths, trees and cycles in graphs, reconfiguration problems on graphs, and degree-constrained spanning trees.
51本色, Board of Governors Excellence in Service and Engagement Award, 2023
I am interested in supervising graduate students students and post-docs in research projects in graph structure and algorithms, and in supervising undergraduate students in these and other areas of discrete mathematics.
- K. Cameron, A parity theorem about trees with specified degrees, Discrete Applied Mathematics 302 (2021), 48-55.
- K. Cameron, S. Huang and O. Merkel, An optimal χ-bound for (P6, diamond)-free graphs, Journal of Graph Theory 97 (2021), 451-465.
- K. Cameron, J. Goedgebeur, S. Huang and Y. Shi, k-Critical graphs in P5-free graphs, Theoretical Computer Science 864 (2021), 80-91.
- K. Cameron and K. Vušković, Hadwiger’s conjecture for hereditary classes of graphs, Bulletin of the European Association for Theoretical Computer Science 131 (2020).
- K. Cameron and C. Thomassen, Cycles containing all the odd-degree vertices, Journal of Combinatorial Theory Series B 143 (2020), 219-225.
- K. Cameron, S. Huang, I. Penev, V. Sivaraman, The class of (C4, C5, P7)-free graphs: Decomposition, χ-boundedness, algorithms, Journal of Graph Theory 93 (2020), 503-552.
- K. Cameron, M. da Silva, S. Huang and K. Vušković, Structure and algorithms for (cap, even hole)-free graphs, Discrete Mathematics 341(2) (2018), 463-473.
- K. Cameron, S. Chaplick and C. Hoàng, On the structure of (pan, even hole)-free graphs, Journal of Graph Theory 87(1) (2018), 108-129.
- K. Cameron, E. Eschen, C. Hoàng, and R. Sritharan, The complexity of the list partition problem for graphs, SIAM Journal on Discrete Mathematics 21 (2007), 900-929.
- K. Cameron and P. Hell, Independent packings in structured graphs, Mathematical Programming Series B 105 (2006), 201-213.
- K. Cameron, Thomason’s algorithm for finding a second hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk’s graphs, Discrete Mathematics 235 (2001), 69-77.
- K. Cameron and J. Edmonds, Some graphic uses of an even number of odd nodes, Annales de l’Institut Fourier 49 (1999), 815-827.
University of Regina Interview
Contact Info:
Office location: LH3041
Languages spoken: English