Dr. Richard BrewsterProfessor | Faculty of Science
Email: rbrewster@tru.ca
Phone: 250-828-5215
Interests
I 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 Interests
Discrete 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.
Education
Ph.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
Publications
Selected Papers in Refereed Journals:
R. C. Brewster, B. Moore, Characterizing circular colouring mixing for p/q < 4 J. Graph Theory 102
(2023), no. 2, 271-294.
J. Bok, R. C. Brewster, T. Feder, P. Hell, N. Jedlickova, List homomorphism problems for signed trees,
Discrete Math. 346 (2023), no. 3, Paper No. 113257, 24 pp.
J. Bok, R. C. Brewster, P. Hell, N. Jedlickova, A. Rafiey, Min orderings and list homomorphism
dichotomies for signed and unsigned graphs, Lecture Notes in Comput. Sci., 13568, Springer, Cham, 2022,
510-526.
J. Bok, R. C. Brewster, T. Feder, P. Hell, N. Jedlickova, List homomorphisms to separable signed graphs,
Lecture Notes in Comput. Sci., 13179, Springer, Cham, 2022, 22-35.
R. C. Brewster, A. Kidner, G. MacGillivray, The 2-colouring problem for (m,n)-mixed graphs with
switching is polynomial, Discrete Math. Theor. Comput. Sci. 24 (2022), no. 2, Paper No. 5, 12 pp.
K. Booker, R. C. Brewster, Edge-coloured graph homomorphisms, paths, and duality, J. Combin. Math.
Combin. Comput. 116 (2021), 219-231.
R. C. Brewster, J. Lee, M. Siggers, Reconfiguration of homomorphisms to reflexive digraph cycles,
Discrete Math. 344 (2021), no. 8, Paper No. 112441, 13 pp.
J. Bok, R. C. Brewster, T. Feder, P. Hell, N. Jedlickova, List homomorphism problems for signed graphs,
LIPIcs. Leibniz Int. Proc. Inform., 170, Schloss Dagstuhl. Leibniz-Zentrum fur Informatik, Wadern, 2020,
Art. No. 20, 14 pp.
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),
1334-1343.
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 History
Professor, 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 Taught
Math 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)
