Graham Farr: selected publications

Book chapters

G Farr and J Oxley, The contributions of W.T. Tutte to matroid theory, in: D R Wood, J de Gier, C E Praeger and T Tao (eds.), 2017 MATRIX Annals, MATRIX Book Series 2, Springer, 2019, pp. 343--361. (published version,

K J Edwards and G E Farr, Graph fragmentability, in: L Beineke and R Wilson (eds.), Topics in Structural Graph Theory, Cambridge University Press, 2013, pp. 203--218.

G E Farr, Tutte-Whitney polynomials: some history and generalizations, in: G R Grimmett and C J H McDiarmid (eds.), Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh, Oxford University Press, 2007, pp. 28--52. (.ps, 506KB)

Refereed journal papers

K S Yow, K Morgan and G Farr, Factorisation of greedoid polynomials of rooted digraphs, Graphs and Combinatorics 37 (2021) 2245--2264. (published version, (arXiv preprint, 2018)

H R Dehkordi and G Farr, On the strong Hanani-Tutte theorem, Electronic Journal of Combinatorics 28 (1) (2021) #P1.43 (16pp). (published version, open access,

H R Dehkordi and G Farr, Non-separating planar graphs, Electronic Journal of Combinatorics 28 (1) (2021) #P1.11 (20pp). (published version, open access,

Z Bukovac, G Farr and K Morgan, Short certificates for chromatic equivalence, Journal of Graph Algorithms and Applications 23 (2) (2019) 227--269. (published version, open access,

G E Farr, Binary functions, degeneracy, and alternating dimaps Discrete Mathematics 342 (5) (2019) 1510--1519. (published version, (§4 of arXiv preprint, 2013)

G Farr, Using Go in teaching the theory of computation, SIGACT News 50 (1) (March 2019) 65--78. (published version, (local copy)

G E Farr and A Y Z Wang, Powerful sets: a generalisation of binary matroids, Electronic Journal of Combinatorics 25 (2018) #P3.42 (20pp). (published version, open access) (arXiv preprint, 2017)

G Farr and N B Ho, The Sprague–Grundy function for some nearly disjunctive sums of Nim and Silver Dollar games, Theoretical Computer Science 732 (2018) 46-59. (published version, (arXiv preprint, 2017)

G E Farr, Minors for alternating dimaps, Quarterly Journal of Mathematics 69 (1) (2018) 285--320. (published version, (arXiv preprint, 2013)

G Farr, The probabilistic method meets Go, Journal of the Korean Mathematical Society 54 (4) (2017) 1121--1148. (published version)

G Farr, Cost-effectiveness of algorithms, Discrete Mathematics & Theoretical Computer Science 17 (1) (2015) 201--218. (published version, open access)

R Mo, G Farr and K Morgan, Certificates for properties of stability polynomials of graphs, Electronic Journal of Combinatorics 21 (2014) #P1.66 (25pp). (published version, open access)

R Robinson and G Farr, Graphs with no 7-wheel subdivision, Discrete Mathematics 327 (2014) 9--28. (published version)

G E Farr, Transforms and minors for binary functions, Annals of Combinatorics 17 (2013) 477--493. (published version) (Newton Institute preprint, 2008)

K J Edwards and G E Farr, Improved upper bounds for planarization and series-parallelization of average degree bounded graphs, Electronic Journal of Combinatorics 19 (2) (2012) #P25 (19pp). (published version, open access)

K Morgan and G Farr, Non-bipartite chromatic factors, Discrete Mathematics 312 (2012) 1166--1170. (published version)

M J Englefield and G E Farr, Eigencircles and associated surfaces, Mathematical Gazette 94 (2010) 438--449. (published version)

R Robinson and G E Farr, Structure and recognition of graphs with no 6-wheel subdivision, Algorithmica 55 (2009) 703-728. (published version)

K Morgan and G Farr, Certificates of factorisation for chromatic polynomials, Electronic Journal of Combinatorics 16 (2009) #R74 (29pp). (published version, open access)

K Morgan and G Farr, Certificates of factorisation for a class of triangle-free graphs, Electronic Journal of Combinatorics 16 (2009) #R75 (14pp). (published version, open access)

G E Farr and J Schmidt, On the number of Go positions on lattice graphs, Information Processing Letters 105 (2008) 124--130. (

K Edwards and G Farr, Planarization and fragmentability of some classes of graphs, Discrete Mathematics 308 (2008) 2396--2406. Accepted version (2007): .ps, 226KB; .pdf, 354KB; preprint version (2004): .ps, 205KB; .pdf, 329KB; tech report version (2003): .ps, 213KB; .pdf, 336KB; tech report citation info and abstract.

K. Morgan and G. Farr, Approximation algorithms for the Maximum Induced Planar and Outerplanar Subgraph problems, Journal of Graph Algorithms and Applications 11 (2007) 165--193. (published version, open access)

G E Farr, On the Ashkin-Teller Model and Tutte-Whitney functions, Combinatorics, Probability and Computing 16 (2007) 251--260. (published version)

M J Englefield and G E Farr, Eigencircles of 2x2 matrices, Mathematics Magazine 79 (October 2006) 281--289. Also see eigencircle web page and applet.

G E Farr, The complexity of counting colourings of subgraphs of the grid, Combinatorics, Probability and Computing 15 (2006) 377--383. (published version)

K Edwards and G Farr, On monochromatic component size for improper colourings, Discrete Applied Mathematics 148 (2005) 89--105. (.ps, 244KB; .pdf, 403KB; published version)

G E Farr, Some results on generalised Whitney functions, Advances in Applied Mathematics 32 (2004) 239--262. (published version)

G E Farr, The Go polynomials of a graph, Theoretical Computer Science 306 (2003) 1--18. (

G Farr and P Eades, Skewness of graphs with small cutsets, Graphs and Combinatorics 19 (2003) 177--194.

G E Farr and C S Wallace, The complexity of Strict Minimum Message Length inference, Computer Journal 45 (2002) 285--292.

K Edwards and G Farr, Fragmentability of graphs, Journal of Combinatorial Theory (Series B) 82 (2001) 30--37. (published version)

G E Farr, On problems with short certificates. Acta Informatica 31 (1994) 479--502.

K J Horadam and G E Farr, The conjugacy problem for HNN extensions with infinite cyclic associated groups, Proceedings of the American Mathematical Society 120 (1994) 1009--1015.

G E Farr, A generalization of the Whitney rank generating function. Mathematical Proceedings of the Cambridge Philosophical Society 113 (1993) 267--280.

G E Farr, A correlation inequality involving stable set and chromatic polynomials. Journal of Combinatorial Theory (Series B) 58 (1993) 14--21. (published version)

G E Farr, The complexity of multicolouring, Discrete Mathematics 69 (1988) 219--223. (published version)

G E Farr, The subgraph homeomorphism problem for small wheels, Discrete Mathematics 71 (1988) 129--142. (published version)

G E Farr and C J H McDiarmid, The complexity of counting homeomorphs, Theoretical Computer Science 36 (1985) 345--348. (published version)

Refereed conference papers

G Farr, B Ainsworth, C Avram and J Sheard, Computer history on the move, in: SIGCSE'16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education (Memphis, 2-5 March 2016), ACM, New York, 2016, pp. 528-533. (published version, open access)

S K Chong, G E Farr, L Frost and S Hawley, On pedagogically sound examples in public-key cryptography, in: V. Estivill-Castro and G. Dobbie (eds.), Proc 29th Australasian Computer Science Conf (ACSC 2006) (Hobart, 16--19 January 2006), Conferences in Research and Practice in Information Technology 48, Australian Computer Society, Sydney, pp 63-68. (published version, open access)

K Edwards and G E Farr, An algorithm for finding large induced planar subgraphs, in: P Mutzel, M Juenger and S Leipert (eds.), Graph Drawing: 9th International Symposium, GD 2001 (Vienna, 23--26 September 2001), Lecture Notes in Computer Science 2265, Springer-Verlag, Berlin, pp 75-83.

A R Jansen, D L Dowe and G E Farr, Inductive inference of chess player strategy, in: R Mizoguchi and J Slaney (eds.), Proc 6th Pacific Rim International Conf on Artificial Intelligence (PRICAI 2000) (Melbourne, 28 Aug -- 1 Sep 2000), Lecture Notes in Artificial Intelligence 1886, Springer-Verlag, 2000, pp 61--71.

G E Farr and D R Powell, Unsupervised learning in Metagame, in: N Foo (ed.), Proceedings of the Twelfth Australian Joint Conference on Artificial Intelligence (AI'99) (Sydney, 6--10 December 1999), Lecture Notes in Artificial Intelligence 1747, Springer-Verlag, 1999, pp 24--35.

D L Dowe, G E Farr, A J Hurst and K L Lentin, Information-theoretic football tipping, Third Conference on Mathematics and Computers in Sport, Bond University, Gold Coast, 1996, pp 233--241.

G E Farr and H Schroeder, An evaluation of reconfiguration algorithms in fault tolerant processor arrays, in: Jonathan Allen and F Thomson Leighton (eds.), Advanced Research in VLSI: Proceedings of the 5th MIT Conference, MIT Press, Cambridge, Ma., USA, 1988, pp 131--148.

G E Farr, Graph colouring and language separability, in: Proceedings of the 10th Australian Computer Science Conference (Deakin University, 4--6 February 1987), Australian Computer Science Communications 9 (1987) 96--105.

Other publications

G Farr, Remembering Bill Tutte: another brilliant codebreaker from World War II, The Conversation, 12 May 2017, (open access)

G Farr, The Man Who Knew Infinity: inspiration, rigour and the art of mathematics, The Conversation, 24 May 2016, (open access)

G Farr, The Imitation Game: is it history, drama or myth?, The Conversation, 9 Jan 2015, (open access)

G Farr, Calls for a posthumous pardon ... but who was Alan Turing?, The Conversation, 22 Dec 2011, (open access)

Last updated 15 November 2021.