Dr Steven Noble

Contact

Mathematical Sciences John Crank 407 Brunel University Uxbridge UB8 3PH United Kingdom

Tel: +44 (0)1895 265619 Fax: +44 (0)1895 269732 Email: steven.noble@brunel.ac.uk Web: Personal Website

Research Interests

Graph theory, complexity of algorithms and combinatorial optimisation, particularly enumeration problems and graph polynomials such as the Tutte polynomial, the frequency assignment problem, graph colouring and labelling problems.

University Research Centre Membership

Research Group Membership

Publications

Journal Papers

(2011) Goodall, AJ., de Mier, A., Noble, SD. and Noy, M., The Tutte Polynomial Characterizes Simple Outerplanar Graphs, COMB PROBAB COMPUT 20 (4) : 609- 616

(2011) Chávez-Lomelí, LE., Merino, C., NOBLE, S. and Ramírez-Ibáñez, M., Some inequalities for the Tutte polynomial, European Journal of Combinatorics 32 422- 433

(2010) Eggemann, N., Havet, F. and Noble, SD., k-L(2,1)-labelling for planar graphs is NP-complete for k >= 4, Discrete Applied Mathematics 158 (16) : 1777- 1788 Download publication

(2009) Eggemann, N. and Noble, SD., Minimizing the oriented diameter of a planar graph, Electronic Notes in Discrete Mathematics 34 267- 271 Download publication

(2009) Merino, C. and Noble, SD., The equivalence of two graph polynomials and a symmetric function, Combinatorics, Probability and Computing 18 (4) : 601- 615 Download publication

(2009) Noble, SD., Evaluating a weighted graph polynomial for graphs of bounded tree-width, The Electronic Journal of Combinatorics 16 (1) : R64 Download publication

(2006) Noble, SD., Evaluating the rank generating function of a graphic 2-polymatroid, Combinatorics, Probability and Computing 15 (3) : 449- 461 Download publication

(2004) Leese, RA. and Noble, SD., Cyclic labellings with constraints at two distances, Electronic Journal of Combinatorics 11 (1) : 1- 16 Download publication

(2004) Koller, AE. and Noble, SD., Domination analysis of greedy heuristics for the frequency assignment problem, Discrete Mathematics 275 (1-3) : 331- 338 Download publication

(2004) Koller, AE. and Noble, SD., Domination analysis of greedy heuristics for the frequency assignment problem, Discrete Mathematics 275 (1-3) : 331- 338

(2004) Krasikov, I. and Noble, SD., Finding next-to-shortest paths in a graph, Information Processing Letters 92 (3) : 117- 119 Download publication

(2003) Calkin, N., Merino, C., Noble, S. and Noy, M., Improved bounds for the number of forests and acyclic orientations in the square lattice, Electronic Journal of Combinatorics 10 (1) : 1- 18 Download publication

(2002) Luczak, MJ. and Noble, SD., Erratum: Optimal arrangement of data in a tree directory: [Discrete Appl. Math 113 (2001) 243–253], Discrete Applied Mathematics 121 (1-3) : 307- 315

(2001) Luczak, M.J.. and Noble, SD., Optimal arrangement of data in a tree directory, Discrete Applied Mathematics 113 (2-3) : 243- 253 Download publication

(2000) Noble, SD. and Welsh, DJA., Knot graphs, Journal of Graph Theory 34 (1) : 100- 111 Download publication

(1999) Noble, SD. and Welsh, DJA., A weighted graph polynomial from chromatic invariants of knots, Annales de l'Institut Fourier 49 (3) : 1057- 1087

(1998) Noble, SD., Evaluating the Tutte polynomial for graphs of bounded tree-width, Combinatorics, Probability and Computing 7 (3) : 307- 321 Download publication

(1996) Noble, SD., Recognising a partitionable simplicial complex is in NP, Discrete Mathematics 152 (1-3) : 303- 305 Download publication

Conference Papers

(1999) Noble, SD. and Welsh, DJA., A weighted graph polynomial from chromatic invariants of knots, Symposium in the Memory of Francois Jaeger, Annales de l'Institute Fourier (49) : 1057- 1087

Book Chapters

(2007) Noble, SD., Complexity of graph polynomials. In: Grimmett, G. and McDiarmid, C. eds. Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh. Oxford University Press 191- 212