photo
 
 
 
 
 
 
 
 
 
 
 
          Pavol Hell


Computational Combinatorics
 
 

Address:
School of Computing Science
Simon Fraser University
BURNABY, B.C., Canada V5A 1S6
phone 778-782-3391, fax 778-782-3045
email address for use by humans:
pavol at (the little spiral) sfu (stands for Simon Fraser University) dot (machines, are you confused yet ?) ca (for Canada)
 

Book GRAPHS AND HOMOMORPHISMS - by Hell and Nesetril

Errata

 

Education:
Charles University, Prague, 1964-68
M.Sc. 1970, McMaster University
Ph.D. 1973, Université de Montréal

The sequence of ancestors in the Mathematics Genealogy Project.
 

Areas of Interest:
Algorithmic Graph Theory
Complexity of Algorithms
Combinatorics of Networks
 

Editorial Boards:
Journal of Graph Theory (Managing Editor)
Discrete Applied Mathematics
 

Affiliated to Organizations:
Pacific Institute of Mathematical Sciences (PIMS)
Mathematics of Information Technology and Computer Science (MITACS)
DIMATIA Prague
Center for Systems Science (CSS)
Center for Experimental and Constructive Mathematics (CECM)
Society for Industrial and Applied Mathematics (SIAM)
SIAG Discrete Math
 

Useful Links:

  • SFU Discrete Math Seminar
  • DIMACS
  • Preprint Server
  • List of Conferences
  • MathSciNet
  • SIGACT Address Book
  • Erdös Number Project
  • The Stony Brook Algorithm Repository
  • Graph Theory Resources
  • World Combinatorics Exchange (and Electronic Journal)
  • Large Graphs with Fixed Degree and Diameter
  • Large Planar Graphs with Fixed Degree and Diameter
  • Data Base of Small Graphs
  • Another List of Home Pages of Combinatorialists
  • Photo of Claude Berge, 1971

    •  

    Graduated Ph.D. Students:

  • KO Chen Shung, Rutgers University Ph.D. 1979 (Broadcasting in Grid Graphs)
  • Martin FARBER, Rutgers University Ph.D. 1982 (LP duality and Strongly Chordal Graphs)
  • ZHOU Hui Shan,  Simon Fraser University Ph.D. 1988 (Homomorphism Properties of Graph Products)
  • Gary MacGILLIVRAY, Simon Fraser University Ph.D. 1989 (The Complexity of Generalized Colourings)
  • HUANG Jing, Simon Fraser University Ph.D. 1992 (Tournament-like Oriented Graphs)
  • Richard BREWSTER, Simon Fraser University Ph.D. 1993 (Homomorphisms of Edge-Coloured Graphs)
  • Bruce BAUSLAUGH, Simon Fraser University  Ph.D. 1994 (Homomorphisms of Infinite Directed Graphs)
  • Roman BACIK, Simon Fraser University  Ph.D. 1996 (Graph Homomorphisms and Semidefinite Programming)
  • Narayan VIKAS, Simon Fraser University  Ph.D. 1997 (Graph Compactions)
  • Reza NASERASR, Simon Fraser University  Ph.D. 2003 (Graph Homomorphisms)
  • Loana Tito NOGUEIRA, Universidade Federal do Rio de Janeiro (with S. Klein and F. Protti);  Ph.D. 2003 (Particionamento de grafos cordais)
  • Cynthia LOTEN, Simon Fraser University  Ph.D. 2004 (Graph Retractions)
  • Juraj STACHO, Simon Fraser University  Ph.D. 2008 (Algorithms for Chordal Graphs)
  • Mehdi KARIMI, Simon Fraser University (co-supervised with Arvind Gupta)  Ph.D. 2009 (Minimum Cost Homomorphisms)

    •  

    Other Supervision:

  • Postdoctoral Fellows
  • M.Sc. Students

    •  

    Monograph:

  • GRAPHS AND HOMOMORPHISMS (with J. Nesetril), Oxford University Press, 2004

    •  

    Selected Publications:

  • Tight upper bounds on messy broadcast time (with H.A. Harutyunyan and A. Liestman), Discrete Applied Math., in press.
  • Adaptable colourings of graph products (with Z.S. Pan, T.L. Wong, and X.D. Zhu), Discrete Math. 309 (2009) 6153--6159.
  • Linear-time certifying algorithms for near-graphical sequences (with D.G. Kirkpatrick), Discrete Math. 309 (2009) 5703--5713.
  • Extension problems with degree bounds (with T. Feder and J. Huang), Discrete Applied Math. 157 (2009) 1592--1599.
  • Polarity of chordal graphs (with D. deWerra, T. Ekim, P. Hell, and J. Stacho), Discrete Applied Math. 156 (2008) 2469--2479.
  • Colouring, constraint satisfaction, and complexity, (with J. Nesetril), Computer Science Review 2 (2008) 143--163.
  • Brooks type theorems for pair list colourings and graph homomorphisms (with T. Feder and J. Huang), SIAM J. Discrete Math. 22 (2008) 1 -- 14.
  • A dichotomy for minimum cost graph homomorphisms (with G. Gutin, A. Rafiey, and A. Yeo), European J. Combinatorics 29 (2008) 900 -- 911
  • On the adaptable chromatic number of graphs (with X. Zhu), European J. Combinatorics 29 (2008) 912 -- 921
  • Oriented star packings (with R.C. Brewster and R. Rizzi), J. Combinatorial Theory B 98 (2008) 558 -- 576
  • Near-unanimity functions and varieties of reflexive graphs (with R.C. Brewster, T. Feder, J. Huang, and G. MacGillivray), SIAM J. Discrete Math. 22 (2008) 938 -- 960
  • On realizations of point determining graphs, and obstructions to full homomorphisms (with T. Feder), Discrete Math. 308 (2008) 1639 -- 1652
  • Density of trigraph homomorphisms (with J. Ne\v{s}et\v{r}il), Graphs and Combinatorics 23 (2007) 275 -- 281
  • The structure of bi-arc trees (with T. Feder and J. Huang), Discrete Math. 307 (2007) 393 -- 401
  • Matrix partitions with finitely many obstructions (with T. Feder and J. Huang), Electronic Journal of Combinatorics R58 14 (2007)
  • List homomorphisms of graphs with bounded degrees (with T. Feder and J. Huang), Discrete Math. 307 (2007) 386 -- 392
  • Digraph matrix partitions and trigraph homomorphisms (with T. Feder and K. Tucker-Nally), Discrete Applied Math. 154 (2006) 2458 -- 2469
  • Full constraint satisfaction problems (with T. Feder), SIAM J. on Computing 36 (2006) 267 -- 293
  • Matrix partitions of perfect graphs (with T. Feder), Discrete Math. 306 (2006) 2450 -- 2460
  • List partitions of chordal graphs (with T. Feder, S. Klein, L.T. Nogueira, and F. Protti), Theoretical Computer Science 349 (2005) 52 - 66
        Companion paper `Chordal Obstructions to M-partitions'
        LATIN2004 version
  • Packing r-cliques in weighted chordal graphs (with S. Klein, L.T. Nogueira, and F. Protti), Annals of OR 138 (2005) 179 - 187
  • The k-piece packing problem (with D. Hartvigsen and J. Szabo), to appear in J. Graph Theory
  • List homomorphisms of graphs with bounded degrees (with T. Feder and J. Huang), to appear in Discrete Math.
  • Certifying LexBFS recognition algorithms for proper inteval graphs and proper interval bigraphs
        (with J. Huang), SIAM J. Discrete Math. 18 (2005) 554 - 570
  • Partitioning chordal graphs into independet sets and cliques
        (with S. Klein, L.T. Nogueira, and F. Protti), Discrete Applied Math. 141 (2004) 185 - 194
  • Spanning spiders and light-splitting switches
        (with L. Gargano, M. Hammar, L. Stacho, and U. Vaccaro), Discrete Math. 285 (2004) 83 - 95
  • Interval bigraphs and circular arc graphs (with J. Huang), J. Graph Theory 46 (2004) 313 - 327
  • Counting list homomorphisms for graphs with bounded degrees (with J. Nesetril),
        in `Graphs, Morphisms and Statistical Physics', DIMACS Series in Discrete Mathematics and
       Theoretical Computer Science 63 (2004) 105 - 112
  • Acyclic homomorphisms and circular colorings of digraphs (with T. Feder and B. Mohar),
        SIAM J. on Discrete Math. 17 (2003) 161 - 169
  • Algorithmic aspects of graph homomorphisms, in `Survey in Combinatorics 2003', London Math. Society
        Lecture Note Series 307, Cambridge University Press, pp. 239 - 276
  • Bi-arc graphs and the complexity of list homomorphisms (with T. Feder and J. Huang),
        J. Graph Theory 42 (2003) 61 - 80
  • Packing paths in digraphs (with R. Brewster, S. Pantel, R. Rizzi, and A. Yeo),
        J. Graph Theory 44 (2003) 81-94
  • List partitions (with T. Feder, S. Klein, and R. Motwani),
        SIAM J. Discrete Math., 16 (2003) 449-478
        STOC99 version Thirty First Annual ACM Symposium on Theory of Computing 1999, pp.464-472
  • Antidirected Hamiltonian paths between specified vertices of a tournament (with M. Rosenfeld),
        Discrete Applied Math 117 (2002) 87 - 98
  • Colouring all directed paths in a symmetric tree, with an application to optical networks
        (with Luisa Gargano and Stephane Perennes), J. Graph Theory 38 (2001) 183 - 186
  • Graphs with a forbidden minor are nearly bipartite (with A. Galluccio and L. Goddyn),
        J. Combinatorial Theory, (B) 83 (2001) 1 - 14
  • A fully dynamic algorithm for recognizing and representing proper interval graphs
        (with R. Shamir and R. Sharan) SIAM J. Computing 31 (2001) 289 - 305
        ESA99 version Seventh Annual European Symposium on Algorithms 1999, pp. 527-539
  • Packings in graphs,  Electronic Notes in Discrete Mathematics volume 5 (2000)
  • The complexity of H-colouring of bounded degree graphs (with A. Gallucio and J. Nesetril),
        Discrete Applied Math. 222 (2000) 101 - 109
  • The circular chromatic number of series-parallel graphs,
        (with X. Zhu), J. Graph Theory 33 (2000) 14 - 24
  • List homomorphisms and circular arc graphs (with T. Feder and J. Huang),
        Combinatorica 19 (1999) 487 - 505
  • List homomorphisms to reflexive graphs (with T. Feder),
        J. Combinatorial Theory B 72 (1998) 236 - 250.
  • Duality and polynomial testing of tree homomorphisms
        (with J. Nesetril and X. Zhu) Trans. Amer. Math. Soc. 348 (1996) 1281-1297
  • On the complexity of H-colouring (with J. Nesetril),
        J. Combinatorial Theory B 48 (1990) 92-110
  • Bandwidth versus bandsize, (with P. Erdös and P. Winkler),
       Annals of Discrete Math. 41 (1989) 117 - 130
  • On the history of the minimum spanning tree problem (with Ron L. Graham),
        Annals of the History of Computing 7 (1985) 43 - 57
  • Sorting and graphs (with B. Bollobas), Invited Chapter in `Graphs and Order',
        D. Reidel ASI Series 147 (1985) 169 - 184
  • Packings by cliques and by finite families of graphs (with David G. Kirkpatrick),
        Discrete Math. 49 (1984) 45 - 59
  • On the complexity of general graph factor problems, (with D.G. Kirkpatrick),
        SIAM J. Computing 12 (1983) 601 - 609.
  • Parallel sorting with constant time for comparisons (with Roland Haggkvist),
        SIAM J. Computing 10 (1981) 465 - 472
  • Retracts in graphs , in `Graphs and Combinatorics',
        Springer-Verlag Lecture Notes in Mathematics 406 (1974) 291 - 301
  • An introduction to the category of graphs,  Annals of the N.Y. Acad. Sc. 328 (1979) 120 - 136

    •  

    Other Publications:

  • More selected publications, in html
  • A full list of all publications, in postscript

    • Back to Faculty Home Page