2024
Strong Cocomparability Graphs and Slash-Free Orderings of Matrices.
SIAM J. Discret. Math., March, 2024
Bi-arc Digraphs: Recognition Algorithm and Applications.
Proceedings of the LATIN 2024: Theoretical Informatics, 2024
2023
On the Kernel and Related Problems in Interval Digraphs.
Algorithmica, June, 2023
Template-driven rainbow coloring of proper interval graphs.
Discret. Appl. Math., March, 2023
List homomorphism problems for signed trees.
Discret. Math., 2023
Describing hereditary properties by forbidden circular orderings.
Appl. Math. Comput., 2023
2022
Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs.
Proceedings of the LATIN 2022: Theoretical Informatics, 2022
List Homomorphisms to Separable Signed Graphs.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2022
2021
Strong Chordality of Graphs with Possible Loops.
SIAM J. Discret. Math., 2021
Distance-two colourings of Barnette graphs.
Eur. J. Comb., 2021
In praise of homomorphisms.
Comput. Sci. Rev., 2021
2020
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
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
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
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
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
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
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
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
Achromatic numbers and graph operations.
Discret. Math., 1992
On the complexity of colouring by superdigraphs of bipartite graphs.
Discret. Math., 1992
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
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
