Dr. Richard Brewster
InterestsI am interested in the interplay of Discrete Mathematics and Computing Science. Many combinatorial problems resist efficient algorithmic solutions due to combinatorial "blow-up". (The haystack is too big to find the needle.) Others admit efficient solutions based on complementary mathematical theory. We aim to classify problems by their computational complexity, including developing new mathematics to create efficient algorithms where possible.
Research InterestsDiscrete mathematics; theoretical computer science; computational complexity; graph theory; polynomial time algorithms and good characterizations; graph homomorphisms and colouring problems; domination problems; graph packings and coverings.
EducationPh.D. (Mathematics), Simon Fraser University, 1993 Thesis:"Vertex colourings of edge-coloured graphs"
M.Sc.(Mathematics), University of Victoria, 1988 Thesis:"Irredundant Ramsey numbers"
B.Sc.(Honours, Combined Mathematics and Computer Science), University of Victoria, 1987
Assoc. Dip. of Science, Cariboo College, 1984
PublicationsSelected Papers in Refereed Journals:
R. C. Brewster, J. Lee, B. Moore, J. Noel, M. Siggers, Graph Homomorphism Reconfiguration and Frozen H-Colourings. J. Graph Theory, 94 (2020), 398???420.
L. Beaudou, R. C. Brewster, F. Foucaud, Broadcast dominationand multipacking: bounds and the integrality gap. Australas. J. Combin., 74 (2019), 86???97.
L. Beaudou, R. C. Brewster, On the multipacking number of grid graphs. Discrete Mathematics & Theoretical Computer Science, 21 (2019)
R. C. Brewster, G. MacGillivray, F. Yang, Broadcast domination and multipacking in strongly chordal graphs, Discrete Applied Math. 261 (2019), 108???118.
R. C. Brewster, M. Siggers. A complexity dichotomy for signed H-colouring. Discrete
Math. 341 (2018), 2768???2773.
R. C. Brewster, J. Lee, M. Siggers. Recolouring Reflexive Digraphs. Discrete Math.
341 (2018), 1708???1721.
R. C. Brewster, F. Foucaud, P. Hell, R. Naserasr. The complexity of signed graph and edge-coloured graph homomorphisms. Discrete Math. 340 (2017), no. 2, 223???235.
R. C. Brewster, Richard C. S. McGuinness, B. Moore, J. A. Noel. A dichotomy theorem for circular colouring reconfiguration. Theoret. Comput. Sci. 639 (2016), 1???13.
R. C. Brewster R, A. Martens, The reconstruction number of a lexicographic sum of cliques, Journal of Combinatorial Mathematics and Combinatorial Computing, 96 (2016), 223???233.
R. C. Brewster R, J. A. Noel, Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings, Journal of Graph Theory, 80 (2015), 173???198. doi: 10.1002/jgt.21846
R. C. Brewster, M. H. Nielsen, S. McGuinness, Factors in Graphs with Multiple Degree Constraints, SIAM J. on Discrete Mathematics, 27 (2013), 1734-1747.
R. C. Brewster, C. M. Mynhardt and L. E. Teshima, New bounds for the broadcast domination number of a graph, Central European Journal of Mathematics, 11 (2013),
R. C. Brewster, G. Hahn, S. W. Lamont, C. Lipka, Lexicographic products with high reconstruction numbers, Discrete Mathematics, 312 (2012) 1638-1645.
R. C. Brewster, J. Noel, Extending precolourings of circular cliques, Discrete Mathematics, 312 (2012) 35-41.
R. C. Brewster, D. Funk, Hamilton circles in 6-edge-connected infinite graphs, J of Graph Theory, 71 (2012) 182-191.
Employment HistoryProfessor, TRU, 08/2009
Associate Professor, TRU, 08/2003
Associate Professor, Bishop's University, 07/2002 06/2003
Assistant Professor, Bishop's University, 07/2001 06/2002
Instructor, Capilano College, 08/1992 07/2001
Courses TaughtMath 114: Calculus I
Math 117: Calculus for Business
Math 124: Calculus II
Math 138/Comp 138: Discrete Structures
Math 139: Discrete Structures II
Math 165: Math for Computing Science
Math 170: Discrete Mathematics
Math 222/Comp 220: Discrete Mathematics
Math 270: Discrete Mathematics 2
Math 322: Abstract Algebra
Math 307: Linear Algebra 2
Math 312: Elementary Number Theory
Math 317: Calculus IV
Math 340: Linear Programming
Math 351: Problem Solving
Math 441: Discrete Optimization
Math 443: Graph Theory
Math 498: Directed Studies Graph Homomorphisms, Finite Geometries
Math 499 : Selected Topics Polyhedral Matching Theory, Nonlinear programming, Algebraic Graph Theory, Algorithmic Graph Theory, Combinatorial Reconfiguration
Comp 309: Introduction to OS (Bishops)
Math 457: Selected Topics in Math (Bishops)
Comp 305: Theoretical CS (Bishops)
Comp 101: Introduction to CS (Bishops)
Comp 216: Data Communications (Bishops)