Pavol Hell | Academic Influence

Pavol Hell's AcademicInfluence.com Rankings

Pavol Hell

Mathematics

#2229

World Rank

#3476

Historical Rank

Graph Theory

#42

World Rank

#49

Historical Rank

Measure Theory

#1636

World Rank

#2017

Historical Rank

mathematics Degrees

Pavol Hell

Computer Science

#5444

World Rank

#5752

Historical Rank

Database

#4332

World Rank

#4505

Historical Rank

computer-science Degrees

Download Badge

Mathematics
Computer Science

Pavol Hell's Degrees

Bachelors Mathematics Comenius University

Similar Degrees You Can Earn

Best Online Bachelor's in Math 2025

Why Is Pavol Hell Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Pavol Hell is a Canadian mathematician and computer scientist, born in Czechoslovakia. He is a professor of computing science at Simon Fraser University. Hell started his mathematical studies at Charles University in Prague, and moved to Canada in August 1968 after the Warsaw Pact invasion of Czechoslovakia. He obtained his MSc from McMaster University in Hamilton, under the joint supervision of Gert Sabidussi and Alex Rosa, and his PhD at the Universite de Montreal, with Gert Sabidussi. In his PhD research he pioneered, on the suggestion of Gert Sabidussi, the study of graph retracts. He describes his area of interest as "computational combinatorics", including algorithmic graph theory and complexity of graph problems. His current focus is on nicely structured graph classes, and on the complexity of various versions of graph homomorphism problems.

(See a Problem?)

Pavol Hell's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Graphs and homomorphisms (2004) (926)
On the History of the Minimum Spanning Tree Problem (1985) (781)
On the complexity of H-coloring (1990) (686)
The core of a graph (1992) (227)
List Homomorphisms and Circular Arc Graphs (1999) (198)
Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs (1996) (178)
On the Complexity of General Graph Factor Problems (1981) (177)
A note on the star chromatic number (1990) (169)
On the completeness of a generalized matching problem (1978) (161)
List Homomorphisms to Reflexive Graphs (1998) (159)
List Partitions (2003) (140)
Graph Problems Arising from Wavelength-Routing in All-Optical Networks (2004) (136)
Complexity of graph partition problems (1999) (122)
Duality and Polynomial Testing of Tree Homomorphisms (1996) (115)
Bi-arc graphs and the complexity of list homomorphisms (2003) (114)
Interval bigraphs and circular arc graphs (2004) (111)
On multiplicative graphs and the product conjecture (1988) (90)
Colouring, constraint satisfaction, and complexity (2008) (88)
Graph decompositions, handcuffed prisoners and balanced P-designs (1972) (75)
Partitioning chordal graphs into independent sets and cliques (2004) (74)
The Complexity of Colouring by Semicomplete Digraphs (1988) (70)
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs (1999) (69)
Spanning Trees with Bounded Number of Branch Vertices (2002) (69)
The effect of two cycles on the complexity of colourings by directed graphs (1989) (66)
Sparse broadcast graphs (1992) (64)
Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs (2005) (64)
A dichotomy for minimum cost graph homomorphisms (2008) (61)
Broadcasting in Bounded Degree Graphs (1992) (57)
Packings by cliques and by finite families of graphs (1984) (55)
Absolute retracts in graphs (1974) (55)
Absolute Retracts and Varieties of Reflexive Graphs (1987) (54)
Complexity of Tree Homomorphisms (1996) (54)
Graph with given achromatic number (1976) (52)
A simple existence criterion for (g (1990) (49)
Universality of A-mote Graphs (1993) (49)
Concerning the achromatic number of graphs (1986) (49)
Spanning spiders and light-splitting switches (2004) (48)
Independent packings in structured graphs (2006) (48)
AN INTRODUCTION TO THE CATEGORY OF GRAPHS * (1979) (47)
Complexity of coloring graphs without paths and cycles (2013) (46)
The complexity of H-colouring of bounded degree graphs (2000) (46)
List matrix partitions of chordal graphs (2005) (46)
Full Constraint Satisfaction Problems (2006) (45)
Large Planar Graphs with Given Diameter and Maximum Degree (1995) (44)
Colouring Paths in Directed Symmetric Trees with Applications to WDM Routing (1997) (44)
The dichotomy of list homomorphisms for digraphs (2010) (44)
The circular chromatic number of series-parallel graphs (2000) (43)
Homomorphisms to oriented paths (1994) (42)
Packings by complete bipartite graphs (1986) (41)
On Restricted Two-Factors (1988) (40)
Tournament-like oriented graphs (1992) (40)
The complexity of signed graph and edge-coloured graph homomorphisms (2015) (38)
Matrix partitions of perfect graphs (2006) (38)
Generalized Colourings (Matrix Partitions) of Cographs (2006) (38)
High-Girth Graphs Avoiding a Minor are Nearly Bipartite (2001) (37)
Local Tournaments and Proper Circular Arc Gaphs (1990) (36)
Parallel Sorting with Constant Time for Comparisons (1981) (36)
Absolute Reflexive Retracts and Absolute Bipartite Retracts (1993) (36)
The Existence of Homomorphisms to Oriented Cycles (1995) (36)
Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs (1995) (35)
Counting List Homomorphisms and Graphs with Bounded Degrees (2001) (35)
Algorithmic aspects of graph homomorphisms (2003) (35)
Polarity of chordal graphs (2008) (35)
Influence diffusion in social networks under time window constraints (2013) (34)
Graphs and k-Societies (1970) (33)
On realizations of point determining graphs, and obstructions to full homomorphisms (2008) (32)
Absolute planar retracts and the four color conjecture (1974) (32)
Graph partitions with prescribed patterns (2014) (31)
On the ultimate independence ratio of a graph (1995) (31)
Retractions to Pseudoforests (2010) (31)
Algorithmic Aspects in Information and Management (2014) (30)
Largest planar graphs of diameter two and fixed maximum degree (1993) (30)
List homomorphisms of graphs with bounded degrees (2007) (30)
The Complexity of Finding Generalized Paths in Tournaments (1983) (29)
Sorting and Merging in Rounds (1982) (29)
Digraph matrix partitions and trigraph homomorphisms (2006) (29)
Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms (2012) (29)
A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs (1996) (29)
Algorithms for Degree Constrained Graph Factors of Minimum Deficiency (1993) (28)
Two algorithms for general list matrix partitions (2005) (27)
From Graph Colouring to Constraint Satisfaction: There and Back Again (2006) (27)
On Injective Colourings of Chordal Graphs (2008) (27)
Independence ratios of graph powers (1994) (27)
On the adaptable chromatic number of graphs (2008) (26)
Minimum Cost Homomorphisms to Reflexive Digraphs (2007) (26)
Bi‐arc graphs and the complexity of list homomorphisms (2003) (25)
Near-Unanimity Functions and Varieties of Reflexive Graphs (2008) (25)
Two remarks on circular arc graphs (1997) (25)
Homomorphisms to oriented cycles (1993) (24)
Optimal Wavelength-routed Multicasting (1998) (24)
Acyclic Homomorphisms and Circular Colorings of Digraphs (2003) (24)
Analogues of the Shannon Capacity of a Graph (1982) (23)
Matrix Partitions with Finitely Many Obstructions (2007) (23)
On the complexity of colouring by superdigraphs of bipartite graphs (1992) (22)
On Generalized Matching Problems (1981) (22)
Ordering without Forbidden Patterns (2014) (20)
Hereditarily hard H-colouring problems (1995) (20)
Sorting and Graphs (1985) (20)
Graph Packings (2000) (20)
Approximation of Minimum Cost Homomorphisms (2012) (19)
Full embeddings into some categories of graphs (1972) (17)
Algorithmic aspects of combinatorics (1978) (17)
The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs (2012) (16)
Adjusted Interval Digraphs (2009) (16)
GRAPHS WITH FORBIDDEN HOMOMORPHIC IMAGES (1979) (16)
Every finite graph is a full subgraph of a rigid graph (1971) (16)
Computational complexity of graph compaction (1997) (15)
Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm (2014) (15)
Some results on the Oberwolfach problem (1974) (15)
Space complexity of list H-colouring: a dichotomy (2013) (15)
Linear-time certifying algorithms for near-graphical sequences (2009) (14)
Groups and Monoids of Regular Graphs (And of Graphs with Bounded Degrees) (1973) (14)
Fast Algorithms for Finding Hamiltonian Paths and Cycles in In-Tournament Digraphs (1993) (14)
Generalized Ramsey Theory for Graphs V. the Ramsey Number of a Digraph (1974) (14)
Packing r-Cliques in Weighted Chordal Graphs (2005) (14)
On nice graphs (2001) (14)
On chordal proper circular arc graphs (1994) (14)
On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs (1993) (13)
Homomorphisms of graphs and of their orientations (1978) (13)
On generalized split graphs (2001) (12)
Graphs Admitting k-NU Operations. Part 1: The Reflexive Case (2013) (12)
Adaptable chromatic number of graph products (2009) (12)
On some strongly rigid families of graphs and the full embeddings they induce (1974) (12)
A simple combinatorial interpretation of certain generalized Bell and Stirling numbers (2013) (12)
Constructions of large planar networks with given degree and diameter (1998) (12)
Achromatic numbers and graph operations (1992) (12)
On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs (2014) (12)
Cohomomorphisms of graphs and hypergraphs (1979) (11)
Bandwidth versus Bandsize (1988) (11)
The k‐piece packing problem (2006) (11)
Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy (2015) (11)
The k-piece packing problem (2006) (10)
On homomorphisms to acyclic local tournaments (1995) (10)
Duality for Min-Max Orderings and Dichotomy for Min Cost Homomorphisms (2009) (10)
Extension problems with degree bounds (2009) (9)
Coloring all directed paths in a symmetric tree, with an application to optical networks * (2001) (9)
Monotone Proper Interval Digraphs and Min-Max Orderings (2012) (9)
The complexity of tropical graph homomorphisms (2016) (9)
Oriented star packings (2008) (9)
COLLECTING AUTOGRAṔHS: n‐NODE GRAPHS THAT HAVE n‐INTEGER SIGNATURES 1 (1979) (9)
Bi-Arc Digraphs and Conservative Polymorphisms (2016) (9)
Packing Problems in Edge-colored Graphs (1994) (9)
Intersection Dimension of Bipartite Graphs (2014) (9)
Multiplicativity of Oriented Cycles (1994) (9)
THE PARTIAL ORDER OF GRAPHS AND HOMOMORPHISMS (2004) (8)
Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs (2006) (8)
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms: Preface (2006) (8)
Strict chordal and strict split digraphs (2017) (8)
Partitioning Chordal Graphs (2011) (7)
Homomorphisms to powers of digraphs (2002) (7)
Coloring all directed paths in a symmetric tree (2001) (7)
Ferrers dimension of grid intersection graphs (2017) (7)
Finding an Antidirected Hamiltonian Path Starting with a Forward Arc from a Given Vertex of a Tournament (1995) (7)
Recognition and Representation of Proper Circular Arc Graphs (1992) (7)
On homomorphisms to edge-coloured cycles (2000) (7)
Broadcasting in one dimension (1988) (6)
Messy broadcasting - Decentralized broadcast schemes with limited knowledge (2011) (6)
On the problem of bandsize (1987) (6)
Point determining digraphs, {0, 1}-matrix partitions, and dualities in full homomorphisms (2013) (6)
Construction of Large Packet Radio Networks (1992) (6)
List homomorphism problems for signed graphs (2020) (6)
Dichotomy for tree-structured trigraph list homomorphism problems (2010) (6)
Packing paths in digraphs (2003) (6)
Distance-two colourings of Barnette graphs (2020) (5)
Brooks-Type Theorems for Pair-List Colorings and List Homomorphisms (2008) (5)
Interval-Like Graphs and Digraphs (2018) (5)
The structure of bi-arc trees (2007) (5)
Images of Rigid Digraphs (1991) (5)
Counterexamples to theorems of Menger type for the diameter (1983) (5)
Factors and Flows (1986) (5)
On the Density of Sets Containing No k-Element Arithmetic Progression of a Certain Kind (1976) (5)
Recognition and Characterization of Chronological Interval Digraphs (2013) (5)
The complexity of restricted graph homomorphisms (1997) (5)
Matrix partitions of split graphs (2013) (5)
Semilattice polymorphisms and chordal graphs (2014) (5)
Cycle transversals in bounded degree graphs (2009) (5)
A note onf-factors in directed and undirected multigraphs (1986) (4)
Hamiltonian Cycles in Covering Graphs of Trees (2017) (4)
Algebraic graph theory - a volume dedicated to Gert Sabidussi on the occasion of his 80th birthday (2012) (4)
Homomorphism Interpolation and Approximation (1982) (4)
Obstructions to partitions of chordal graphs (2013) (4)
Matroids With Weighted Bases and Feynman Integrals (1984) (4)
Min-Orderable Digraphs (2020) (4)
Rounding in Symmetric Matrices and Undirected Graphs (1996) (4)
Counting Partitions of Graphs (2012) (4)
On edge-sets of bicliques in graphs (2012) (4)
Equicovering matroids by distinct bases (1995) (3)
Complexity of Correspondence Homomorphisms (2017) (3)
Faithful Representations of Graphs by Islands in the Extended Grid (2010) (3)
Broadcasting in generalized chordal rings (2003) (3)
Connected obstructions to full graph homomorphisms (2014) (3)
Minimal obstructions to 2-polar cographs (2017) (3)
Antidirected hamiltonian paths between specified vertices of a tournament (2002) (3)
Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints (2019) (3)
Graphs Admitting k-NU Operations. Part 2: The Irreflexive Case (2014) (3)
Graph endpoint coloring and distributed processing (1993) (3)
List Partitions of Chordal Graphs (2004) (3)
Bipartite Analogues of Comparability and Cocomparability Graphs (2020) (3)
Blocking Quadruple: A New Obstruction to Circular-Arc Graphs (2014) (3)
Spanningspiders and lig ht-splittingswitches (2004) (3)
Some results on the Oberwolfach problem (1974) (3)
Describing hereditary properties by forbidden circular orderings (2021) (2)
Corrections: Generalized Ramsey Theory for Graphs V (1975) (2)
On the Kernel and Related Problems in Interval Digraphs (2021) (2)
The Existence Problem for Graph Homomorphisms (1988) (2)
Jump number and width (1986) (2)
On the Edge-sets of Rigid and Corigid Graphs (1979) (2)
Minimal digraph obstructions for small matrices (2016) (2)
Vertex arboricity of cographs (2019) (2)
Colourings, homomorphisms, and partitions of transitive digraphs (2015) (2)
Obstructions to chordal circular-arc graphs of small independence number (2012) (2)
Join colourings of chordal graphs (2015) (2)
Broadcasting in planar graphs (1998) (2)
Strong Chordality of Graphs with Possible Loops (2021) (1)
Minimum Cost Homomorphisms with Constrained Costs (2016) (1)
Small H-Coloring Problems for Bounded Degree Digraphs (2012) (1)
Correspondence Homomorphisms to Reflexive Graphs (2017) (1)
In praise of homomorphisms (2021) (1)
An intermediate value theorem for graphs with given automorphism group (1979) (1)
Strongly chordal digraphs and Γ-free matrices (2019) (1)
On the Density of Trigraph Homomorphisms (2007) (1)
Distance-Two Colorings of Barnette Graphs (2018) (1)
List homomorphism problems for signed trees (2023) (1)
A generalization of the theorem of Lekkerkerker and Boland (2005) (1)
(g,f) - Factors \& Packings, When g>f: Characterizations \& Algorithms (1983) (1)
Partitioning Cographs into Two Forests and One Independent Set (2020) (1)
List Homomorphisms to Separable Signed Graphs (2022) (1)
THE STRUCTURE OF COMPOSITION (2004) (0)
H-coloring degree-bounded (acyclic) digraphs (2014) (0)
COLOURING—VARIATIONS ON A THEME (2004) (0)
Generalizations of Interval Graphs (2009) (0)
Comparability and Cocomparability Bigraphs (2019) (0)
C C ] 2 2 A ug 2 01 6 Minimum Cost Homomorphisms with Constrained Costs (2018) (0)
Algorithmic aspects of graph homomorphisms Pavol Hell (2008) (0)
DISTANCE-TWO COLORINGS OF CUBIC PLANAR GRAPHS (2018) (0)
Strong cocomparability graphs and Slash-free orderings of matrices (2022) (0)
Min orderings and list homomorphism dichotomies for signed and unsigned graphs (2022) (0)
Chordal (2,1) - graphs (2000) (0)
Sorting, Scheduling, Computing, Operations Research, and Social Science (1985) (0)
A generalization ofthe theorem ofLekkerkerker and Boland (2005) (0)
Biography of Martin Farber, 1951-1989 (1993) (0)
Complexity of correspondence H-colourings (2020) (0)
Template-Driven Rainbow Coloring of Proper Interval Graphs (2023) (0)
All Minimal Cograph Obstructions for Arboricity 2 (2019) (0)
Graph homomorphisms (2021) (0)
Three-and-more set theorems (2000) (0)
Preface (2015) (0)
SOME NOTES ON NUF DIGRAPHS (2006) (0)
Adjusted Interval Digraphs and Complexity of List Homomorphisms Tomás Feder Pavol Hell Jing Huang Arash Rafiey (2010) (0)
Preface (2012) (0)
Sidepath results on packing $\vec{P}_1$'s and $\vec{P}_2$'s (2003) (0)
Strongly chordal digraphs and $\Gamma$-free matrices. (2019) (0)
PRODUCTS AND RETRACTS (2004) (0)
TESTING FOR THE EXISTENCE OF HOMOMORPHISMS (2004) (0)
Distance-Two Coloring of Barnette Graphs (2018) (0)
Minimum Weighted Szeged Index Trees (2020) (0)
Adjusted Interval Digraphs Tomás Feder Pavol Hell (2008) (0)
On the complexity of coloring areflexive h-ary relations with given permutation group (1998) (0)

This paper list is powered by the following services:

Other Resources About Pavol Hell

en.wikipedia.org

What Schools Are Affiliated With Pavol Hell?

Pavol Hell is affiliated with the following schools: