List of Publications

Joan P. Hutchinson
Professor of Mathematics and Computer Science
Macalester College, St. Paul, MN 55105
Tel. (651) 696-6134



Last updated 15 August 2004
  1. Coloring graphs on surfaces, invited chapter in Topological Graph Theory (J. Gross and T. Tucker, eds.), Topics in Graph Theory series (L. Beineke and R. Wilson, eds.), Cambridge University Press (to appear).
  2. with E. H. Moore, Distance bounds in color extension theorems (preprint).
  3. with A. Dean and E. Gethner, Unit Bar-visibility Layouts of Triangulated Polygons: Extended Abstract, proceedings of 12th International Symposium on Graph Drawing 2004 (to appear).
  4. A note on rectilinear and polar visibility graphs (submitted, Discrete Applied Math).
  5. with Y. Chang, M. S. Jacobson, J. Lehel, and D. B. West, The visibility number of a graph, SIAM J. Discrete Math (to appear).
  6. with M.O. Albertson, Extending precolorings of subgraphs of locally planar graphs, European J. of Combinatorics (submitted as invited contribution to special issue on Topological Graph Theory and Graph Minors).
  7. with M.O. Albertson, Graph Coloring Extensions: When Hadwiger's Conjecture and Embeddings Help, Electronic J. Combinatorics, 9 (1) (2002), R37.
  8. with Bruce Richter and Paul Seymour, Colouring Eulerian Triangulations J. Combinatorial Theory, Series B (to appear).
  9. On 3- and 4-coloring nearly triangulated surfaces, Proc. 32nd Southeastern Conf. on Combinatorics, Graph Theory, and Computing, 2001, Congressus Numerantium 150 (2001) 129-143.
  10. Arc- and Circle-Visibility Graphs, Australasian J. Combinatorics 25 (2002) 241-262.
  11. with D. Archdeacon, A. Nakamoto, S. Negami, and K. Ota, Chromatic Numbers of Quadrangulations of closed surfaces (pdf, permission required), J. Graph Theory, 37 (2001) 100-114.
  12. with G. Chen, W. Piotrowski, W. Shreve, and B. Wei, Degree sequences with repeated values (pdf), Ars Combinatoria 59 (2001), pp. 33-44.
  13. On polar visibility representations of graphs, Graph Drawing, 8th International Symposium, GD 2000, Colonial Williamsburg, VA, Sept. 2000, Proceedings, (J. Marks, ed.), Lecture Notes in Computer Science #1984, Springer, Berlin, 2001, pp. 63 - 76.
  14. with M. O. Albertson, Extending colorings of locally planar graphs ( postscript, dvi, LaTeX), J. Graph Theory, 36 (2001) 105-116.
  15. with Karen L. Collins, Four-coloring six-regular graphs on the torus, Graph Colouring and Applications, P. Hansen and O. Marcotte, eds., CRM Proceedings and Lecture Notes, Vol. 23 (1999) 21-34.
  16. with T. Shermer, A. Vince, On Representations of some Thickness-two graphs (pdf, permission required), Computational Geometry, Theory and Applications, 13 (1999) 161-171.
  17. with A. Dean, Rectangle-visibility layouts of unions and products of trees (compressed postscript, pdf ) , the (electronic) Journal of Graph Algorithms and Applications, 2 (1998) 1-21.
  18. with S. Wagon, Kempe revisited, Amer. Math. Monthly, 105 (1998) 170-174.
  19. _____, Four-coloring Planar Maps, Mathematica in Education and Research, 6, no. 1, (1997) 42 - 51.
  20. with P. Bose, A. Dean, and T. Shermer, On Rectangular Visibility Graphs, Graph Drawing, Lecture Notes in Computer Science #1190 (Symp. on Graph Drawing, GD '96, Berkeley, Calif, USA, Sept. 1996 Proceedings), S. North, ed., Springer-Verlag, Berlin, 1997, pp. 25-44.
  21. with A. Dean, Rectangular Visibility Representations of Bipartite Graphs, Discrete Applied Math 75, (1997) 9-25.
  22. with T. Shermer and A. Vince, On Representations of some Thickness-two Graphs, Extended Abstract, Lecture Notes in Computer Science #1027 (Symposium on Graph Drawing, GD'95, Passau, Germany, Sept. 1995), F. Brandenburg ed., Springer-Verlag, Jan, 1996, pp. 324-332.
  23. Three-coloring graphs embedded on surfaces with all faces even-sided (pdf, permision required), J. Combinatorial Theory, Series B 65 (1995) 139-155.
  24. with A. Davidow, J. P. Huneke, Homeomorphically irreducible spanning trees in planar and toroidal graphs, Graph Theory, Combinatorics, and Applications: Proceedings Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Vol. 1, Y. Alavi and A. Schwenk, eds., John Wiley and Sons, Inc., 1995, pp. 265-276.
  25. with A. Dean, Rectangular Visibility Representations of Bipartite Graphs, Extended Abstract, Lecture Notes in Computer Science #894, Graph Drawing, R. Tamassia and I.G. Tollis, eds., Springer-Verlag, Berlin, 1995, pp. 159-166.
  26. When three people shake the same number of hands, Congressus Numerantium 95 (1993) 31-35.
  27. Coloring ordinary maps, maps of empires, and maps of the Moon Math. Magazine Vol. 66 No. 4, October 1993, 211-225.
  28. Summertime and the livin' is ..., AWM Newsletter, 22 (1992) 9-11.
  29. with J. R. Griggs, On the r-domination number of a graph, Discrete Math, 101 (1992) 65-72. also in Topics in Discrete Mathematics, Vol. 6, North-Holland, Amsterdam, 1992, 395-402.
  30. Book review of N. Hartsfield and G. Ringel's Pearls in Graph Theory, a Comprehensive Introduction, Amer. Math. Monthly 98 (1991) 873-875.
  31. with A. Dean and E. Scheinerman, On the thickness and arboricity of a graph, J. Combinatorial Theory (B), 52 (1991) 147-151.
  32. with A. Dean, Relations among embedding parameters for graphs, Graph Theory, Combinatorics, and Applications, Proc. Sixth Quadrennial Inter national Conf. on the Theory and Applications of Graphs, Western Michigan University, New York, Wiley, 1991.
  33. with M. Albertson, D. Berman, and C. Thomassen, On homeomorphically irrreducible spanning trees, J. Graph Theory, 14 (1990) 247-258.
  34. On genus-reducing and planarizing algorithms for embedded graphs, Graphs and Algorithms, Proceedings of a Summer Research Conference, Boulder, CO, July, 1987, Contemporary Mathematics Series, Amer. Math. Soc., Vol. 89, 1989
  35. On short noncontractible cycles in embedded graphs, SIAM J. Discrete Math, 1(1988) 185-192.
  36. with G. L. Miller, Deleting vertices to make graphs of positive genus planar, Discrete Algorithms and Complexity Theory, Academic Press, Boston, 1986
  37. with L. B. Krompart, Partitions that arise from connected planar graphs with three orbits, Ars Combinatoria 20(1985) 111-124. MR 87c:05063
  38. with L. B. Krompart, Connected planar graphs with three or more orbits, Graph Theory and its Applications to Algorithms and Computer Science, John Wiley & Sons, N.Y. 1985. MR 87a:05079
  39. with S. Wagon, A forbidden subgraph characterization of infinite graphs of finite genus, Graphs and Applications, Proc. First Colorado Symposium on Graph Theory John Wiley & Sons, N.Y. 1985. MR 86b:05025
  40. with J. Gilbert and R. E. Tarjan, A separator theorem for graphs of bounded genus, J. Algorithms 22(1984) 391-407. Also Cornell University, Department of Computer Science Technical Report #82-506.MR 86h:68145
  41. A five color theorem for graphs on surfaces, Proc. Amer. Math. Soc. 90 (1984) 497-504. MR 85d:05115
  42. Automorphism properties of embedded graphs, J. Graph Theory 8 (1984) 35-49.
  43. with E. Gethner, Connected graphs with complementary edge-orbits, Ars Combinatoria 12(1981) 135-146. MR 84h:05065
  44. with G. McNulty, Partitions which are complementary orbits of graphs of genus g, Discrete Math. 45(1983) 255-275. MR 84j:05055
  45. with P. B. Trow, Some pigeonhole principle results extended, Amer. Math. Monthly 87(1980) 648-51. MR 82g:05016
  46. with M. O. Alberston, On six-chromatic toroidal graphs, Proc. London Math. Soc. 41(1980) 533-556 MR 82k:05047b
  47. _____, Hadwiger's conjecture for graphs on the Klein bottle, Discrete Math. 29(1980) 1-11. MR 81a:05046
  48. _____, The three excluded cases of Dirac's map-color theorem, Annals of the N. Y. Academy of Sciences, Volume 319, 7-17. MR 81c:05037
  49. _____, Hadwiger's conjecture and six-chromatic toroidal graphs, Graph Theory and Related Topics. Academic Press, N. Y., 1979. MR 82k:05047a
  50. with S. H. Whitesides, On a generalized regularity condition, Theory and Application of Graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976, Lecture Notes in Mathematics #642, Springer-Verlag, Berlin, 1978. MR 80b:05047
  51. with M. O. Albertson, On the independence number of a graph, J. Graph Theory 2(1978) 1-8. MR 58 #10545 a,b
  52. Let me count the ways: Women in Combinatorics, Association for Women in Mathematics Newsletter 7(1977) 3-7.
  53. with M. O. Alberston, The independence ratio and genus of a graph, Trans. Amer. Math. Soc 226(1977) 161-173. MR 55 #10303
  54. _____, The maximum size of an independent set in a toroidal graph, Proc. Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing, 1975.MR 52 #13453
  55. _____, The maximum size of an independent set in a non-planar graph, Bull. Amer. Math. Soc. 81(1975) 554-5. MR 51 #267
  56. Maps made from Eulerian graphs need fewer colors, Proc. Fifth British Combinatorial Conference, Congr. Numer. 15, 1975. MR 53 #2728
  57. On words with prescribed overlapping subsequences, Utilitas Math. 7(1975) 241-50. MR #12602
  58. with H. S. Wilf, On Eulerian circuits and words with prescribed adjacency patterns, J. Combinatorial Theory (A) 18(1975) 80-7. MR 51 #10115
  59. Eulerian graphs and polynomial identities for skew-symmetric matrices, Canad. J. Math. 27(1975) 590-609. MR 53 #7858
  60. Cancelling Eulerian graphs, Graphs and Combinatorics (R.A. Bari and F. Harary, eds.), Lecture Notes in Mathematics #406, Springer-Verlag, Berlin, 1974. MR 51 #2981
  61. Eulerian graphs and polynomial identities for sets of matrices, Proc. Nat. Acad. Sci. U.S.A. 71(1974) 1314-6. MR 50 #2209

Short Notes


Articles about me and my work

Back to Joan Hutchinson's Homepage

Last updated 15 August 2004