Pavol Hell

According to our database1, Pavol Hell authored at least 187 papers between 1972 and 2021.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Distance-two colourings of Barnette graphs.
Eur. J. Comb., 2021

2020
Min-Orderable Digraphs.
SIAM J. Discret. Math., 2020

Bipartite Analogues of Comparability and Cocomparability Graphs.
SIAM J. Discret. Math., 2020

Hamiltonian cycles in covering graphs of trees.
Discret. Appl. Math., 2020

Complexity of correspondence H-colourings.
Discret. Appl. Math., 2020

List Homomorphism Problems for Signed Graphs.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Partitioning Cographs into Two Forests and One Independent Set.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2020

2019
Minimal obstructions to 2-polar cographs.
Discret. Appl. Math., 2019

Strongly chordal digraphs and Γ-free matrices.
CoRR, 2019

Vertex arboricity of cographs.
CoRR, 2019

Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints.
CoRR, 2019

2018
Distance-Two Colorings of Barnette Graphs.
CoRR, 2018

Interval-Like Graphs and Digraphs.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Distance-Two Coloring of Barnette Graphs.
Proceedings of the 30th Canadian Conference on Computational Geometry, 2018

2017
Correspondence Homomorphisms to Reflexive Graphs.
Electron. Notes Discret. Math., 2017

Colourings, homomorphisms, and partitions of transitive digraphs.
Eur. J. Comb., 2017

The complexity of signed graph and edge-coloured graph homomorphisms.
Discret. Math., 2017

Strict chordal and strict split digraphs.
Discret. Appl. Math., 2017

Complexity of coloring graphs without paths and cycles.
Discret. Appl. Math., 2017

The complexity of tropical graph homomorphisms.
Discret. Appl. Math., 2017

Ferrers dimension of grid intersection graphs.
Discret. Appl. Math., 2017

Complexity of Correspondence Homomorphisms.
CoRR, 2017

2016
Bi-Arc Digraphs and Conservative Polymorphisms.
CoRR, 2016

Minimum Cost Homomorphisms with Constrained Costs.
Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

2015
Preface.
Theor. Comput. Sci., 2015

Influence diffusion in social networks under time window constraints.
Theor. Comput. Sci., 2015

Join colourings of chordal graphs.
Discret. Math., 2015

Point determining digraphs, {0, 1}-matrix partitions, and dualities in full homomorphisms.
Discret. Math., 2015

The complexity of signed graph and 2-edge-coloured graph homomorphisms.
CoRR, 2015

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy.
Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

2014
H-coloring degree-bounded (acyclic) digraphs.
Theor. Comput. Sci., 2014

Blocking Quadruple: A New Obstruction to Circular-Arc Graphs.
SIAM J. Discret. Math., 2014

Graphs Admitting k-NU Operations. Part 2: The Irreflexive Case.
SIAM J. Discret. Math., 2014

Semilattice polymorphisms and chordal graphs.
Eur. J. Comb., 2014

Connected obstructions to full graph homomorphisms.
Eur. J. Comb., 2014

Graph partitions with prescribed patterns.
Eur. J. Comb., 2014

On the complexity of the 3-kernel problem in some classes of digraphs.
Discuss. Math. Graph Theory, 2014

A simple combinatorial interpretation of certain generalized Bell and Stirling numbers.
Discret. Math., 2014

Matrix partitions of split graphs.
Discret. Appl. Math., 2014

Intersection Dimension of Bipartite Graphs.
Proceedings of the Theory and Applications of Models of Computation, 2014

Space complexity of list <i>H</i>-colouring: a dichotomy.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Ordering without Forbidden Patterns.
Proceedings of the Algorithms - ESA 2014, 2014

2013
Graphs Admitting k-NU Operations. Part 1: The Reflexive Case.
SIAM J. Discret. Math., 2013

Obstructions to chordal circular-arc graphs of small independence number.
Electron. Notes Discret. Math., 2013

Obstructions to partitions of chordal graphs.
Discret. Math., 2013

Space complexity of list H-colouring: a dichotomy.
CoRR, 2013

Recognition and Characterization of Chronological Interval Digraphs.
Electron. J. Comb., 2013

Small <i>H</i>-Coloring Problems for Bounded Degree Digraphs.
Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

2012
The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs.
SIAM J. Discret. Math., 2012

Monotone Proper Interval Digraphs and Min-Max Orderings.
SIAM J. Discret. Math., 2012

Preface.
Discret. Math., 2012

On edge-sets of bicliques in graphs.
Discret. Appl. Math., 2012

Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms.
Discret. Appl. Math., 2012

Small H-coloring problems for bounded degree digraphs
CoRR, 2012

Counting Partitions of Graphs.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Approximation of Minimum Cost Homomorphisms.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Partitioning Chordal Graphs.
Electron. Notes Discret. Math., 2011

Messy broadcasting - Decentralized broadcast schemes with limited knowledge.
Discret. Appl. Math., 2011

Dichotomy for tree-structured trigraph list homomorphism problems.
Discret. Appl. Math., 2011

The Dichotomy of List Homomorphisms for Digraphs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010
Retractions to Pseudoforests.
SIAM J. Discret. Math., 2010

Faithful Representations of Graphs by Islands in the Extended Grid.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

2009
Cycle transversals in bounded degree graphs.
Electron. Notes Discret. Math., 2009

Adjusted Interval Digraphs.
Electron. Notes Discret. Math., 2009

Adaptable chromatic number of graph products.
Discret. Math., 2009

Linear-time certifying algorithms for near-graphical sequences.
Discret. Math., 2009

Extension problems with degree bounds.
Discret. Appl. Math., 2009

Duality for Min-Max Orderings and Dichotomy for Min Cost Homomorphisms
CoRR, 2009

Generalizations of Interval Graphs.
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

2008
Brooks-Type Theorems for Pair-List Colorings and List Homomorphisms.
SIAM J. Discret. Math., 2008

Near-Unanimity Functions and Varieties of Reflexive Graphs.
SIAM J. Discret. Math., 2008

Oriented star packings.
J. Comb. Theory, Ser. B, 2008

On the adaptable chromatic number of graphs.
Eur. J. Comb., 2008

A dichotomy for minimum cost graph homomorphisms.
Eur. J. Comb., 2008

On realizations of point determining graphs, and obstructions to full homomorphisms.
Discret. Math., 2008

Polarity of chordal graphs.
Discret. Appl. Math., 2008

Colouring, constraint satisfaction, and complexity.
Comput. Sci. Rev., 2008

On Injective Colourings of Chordal Graphs.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Minimum Cost Homomorphisms to Reflexive Digraphs.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

2007
On the Density of Trigraph Homomorphisms.
Graphs Comb., 2007

Matrix Partitions with Finitely Many Obstructions.
Electron. Notes Discret. Math., 2007

The structure of bi-arc trees.
Discret. Math., 2007

List homomorphisms of graphs with bounded degrees.
Discret. Math., 2007

2006
Full Constraint Satisfaction Problems.
SIAM J. Comput., 2006

Independent packings in structured graphs.
Math. Program., 2006

The <i>k</i>-piece packing problem.
J. Graph Theory, 2006

Matrix partitions of perfect graphs.
Discret. Math., 2006

Digraph matrix partitions and trigraph homomorphisms.
Discret. Appl. Math., 2006

Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs
CoRR, 2006

2005
List matrix partitions of chordal graphs.
Theor. Comput. Sci., 2005

A generalization of the theorem of Lekkerkerker and Boland.
Discret. Math., 2005

Packing <i>r</i>-Cliques in Weighted Chordal Graphs.
Ann. Oper. Res., 2005

Two algorithms for general list matrix partitions.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs.
SIAM J. Discret. Math., 2004

Interval bigraphs and circular arc graphs.
J. Graph Theory, 2004

Polychromatic cliques.
Discret. Math., 2004

Spanning spiders and light-splitting switches.
Discret. Math., 2004

Partitioning chordal graphs into independent sets and cliques.
Discret. Appl. Math., 2004

List Partitions of Chordal Graphs.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Graphs and homomorphisms.
Oxford lecture series in mathematics and its applications 28, Oxford University Press, ISBN: 978-0-19-852817-3, 2004

2003
Acyclic Homomorphisms and Circular Colorings of Digraphs.
SIAM J. Discret. Math., 2003

List Partitions.
SIAM J. Discret. Math., 2003

Broadcasting in generalized chordal rings.
Networks, 2003

Bi-arc graphs and the complexity of list homomorphisms.
J. Graph Theory, 2003

Packing paths in digraphs.
J. Graph Theory, 2003

2002
Homomorphisms to powers of digraphs.
Discret. Math., 2002

Antidirected hamiltonian paths between specified vertices of a tournament.
Discret. Appl. Math., 2002

Spanning Trees with Bounded Number of Branch Vertices.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs.
SIAM J. Comput., 2001

Coloring all directed paths in a symmetric tree, with an application to optical networks.
J. Graph Theory, 2001

High-Girth Graphs Avoiding a Minor are Nearly Bipartite.
J. Comb. Theory, Ser. B, 2001

On generalized split graphs.
Electron. Notes Discret. Math., 2001

On nice graphs.
Discret. Math., 2001

Counting List Homomorphisms and Graphs with Bounded Degrees.
Proceedings of the Graphs, 2001

2000
The circular chromatic number of series-parallel graphs.
J. Graph Theory, 2000

Graph Packings.
Electron. Notes Discret. Math., 2000

On homomorphisms to edge-coloured cycles.
Electron. Notes Discret. Math., 2000

The complexity of <i>H</i>-colouring of bounded degree graphs.
Discret. Math., 2000

1999
List Homomorphisms and Circular Arc Graphs.
Comb., 1999

Complexity of Graph Partition Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998
Constructions of large planar networks with given degree and diameter.
Networks, 1998

List Homomorphisms to Reflexive Graphs.
J. Comb. Theory, Ser. B, 1998

Optimal Wavelength-routed Multicasting.
Discret. Appl. Math., 1998

On the complexity of coloring areflexive h-ary relations with given permutation group.
Ars Comb., 1998

Broadcasting in planar graphs.
Australas. J Comb., 1998

1997
Two remarks on circular arc graphs.
Graphs Comb., 1997

The complexity of restricted graph homomorphisms.
Discret. Math., 1997

Colouring Paths in Directed Symmetric Trees with Applications to WDM Routing.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996
A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs.
SIAM J. Discret. Math., 1996

Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs.
SIAM J. Comput., 1996

Complexity of Tree Homomorphisms.
Discret. Appl. Math., 1996

Rounding in Symmetric Matrices and Undirected Graphs.
Discret. Appl. Math., 1996

1995
The Existence of Homomorphisms to Oriented Cycles.
SIAM J. Discret. Math., 1995

On homomorphisms to acyclic local tournaments.
J. Graph Theory, 1995

Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs.
J. Graph Theory, 1995

On the ultimate independence ratio of a graph.
Eur. J. Comb., 1995

Equicovering matroids by distinct bases.
Eur. J. Comb., 1995

Hereditarily hard H-colouring problems.
Discret. Math., 1995

Large Planar Graphs with Given Diameter and Maximum Degree.
Discret. Appl. Math., 1995

Finding an Antidirected Hamiltonian Path Starting with a Forward Arc from a Given Vertex of a Tournament.
Proceedings of the Combinatorics and Computer Science, 1995

1994
Multiplicativity of Oriented Cycles.
J. Comb. Theory, Ser. B, 1994

Homomorphisms to oriented paths.
Discret. Math., 1994

Independence ratios of graph powers.
Discret. Math., 1994

On chordal proper circular arc graphs.
Discret. Math., 1994

Packing Problems in Edge-colored Graphs.
Discret. Appl. Math., 1994

1993
Graph endpoint coloring and distributed processing.
Networks, 1993

On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs.
J. Graph Theory, 1993

Algorithms for Degree Constrained Graph Factors of Minimum Deficiency.
J. Algorithms, 1993

Universality of A-mote Graphs.
Eur. J. Comb., 1993

Largest planar graphs of diameter two and fixed maximum degree.
Discret. Math., 1993

Biography of Martin Farber, 1951-1989.
Discret. Appl. Math., 1993

Fast Algorithms for Finding Hamiltonian Paths and Cycles in In-Tournament Digraphs.
Discret. Appl. Math., 1993

Absolute Reflexive Retracts and Absolute Bipartite Retracts.
Discret. Appl. Math., 1993

Homomorphisms to oriented cycles.
Comb., 1993

1992
Broadcasting in Bounded Degree Graphs.
SIAM J. Discret. Math., 1992

Construction of Large Packet Radio Networks.
Parallel Process. Lett., 1992

The core of a graph.
Discret. Math., 1992

Achromatic numbers and graph operations.
Discret. Math., 1992

On the complexity of colouring by superdigraphs of bipartite graphs.
Discret. Math., 1992

Sparse broadcast graphs.
Discret. Appl. Math., 1992

Recognition and Representation of Proper Circular Arc Graphs.
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

1991
Images of Rigid Digraphs.
Eur. J. Comb., 1991

1990
A note on the star chromatic number.
J. Graph Theory, 1990

On the complexity of <i>H</i>-coloring.
J. Comb. Theory, Ser. B, 1990

A simple existence criterion for (g<f)- factors.
Discret. Math., 1990

Preface.
Discret. Appl. Math., 1990

The effect of two cycles on the complexity of colourings by directed graphs.
Discret. Appl. Math., 1990

Local Tournaments and Proper Circular Arc Gaphs.
Proceedings of the Algorithms, 1990

1988
On Restricted Two-Factors.
SIAM J. Discret. Math., 1988

The Complexity of Colouring by Semicomplete Digraphs.
SIAM J. Discret. Math., 1988

Broadcasting in one dimension.
Discret. Appl. Math., 1988

On multiplicative graphs and the product conjecture.
Comb., 1988

1987
On the problem of bandsize.
Graphs Comb., 1987

1986
Concerning the achromatic number of graphs.
J. Comb. Theory, Ser. B, 1986

A note on<i>f</i>-factors in directed and undirected multigraphs.
Graphs Comb., 1986

1985
On the History of the Minimum Spanning Tree Problem.
IEEE Ann. Hist. Comput., 1985

1984
Packings by cliques and by finite families of graphs.
Discret. Math., 1984

1983
On the Complexity of General Graph Factor Problems.
SIAM J. Comput., 1983

The Complexity of Finding Generalized Paths in Tournaments.
J. Algorithms, 1983

Counterexamples to theorems of Menger type for the diameter.
Discret. Math., 1983

1981
Parallel Sorting with Constant Time for Comparisons.
SIAM J. Comput., 1981

On Generalized Matching Problems.
Inf. Process. Lett., 1981

1979
An intermediate value theorem for graphs with given automorphism group.
J. Graph Theory, 1979

1978
On the Completeness of a Generalized Matching Problem
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1976
Graph with given achromatic number.
Discret. Math., 1976

1972
Graph decompositions, handcuffed prisoners and balanced P-designs.
Discret. Math., 1972


  Loading...