65 citations · 87 across the 14 of their papers we have counts for
16 papers
Hedetniemi's conjecture and strongly multiplicative graphs
Claude Tardif, Marcin Wrochna
A graph K is multiplicative if a homomorphism from any product G x H to K implies a homomorphism from G or from H. Hedetniemi's conjecture states that all cliques are multiplicativ…
Iterated Arc Graphs
Danny Rorabaugh, Claude Tardif, David Wehlau +1
The arc graph of a digraph is the digraph with the set of arcs of as vertex-set, where the arcs of join consecutive arcs of . In 1981, Poljak and Rödl char…
Logical compactness and constraint satisfaction problems
Danny Rorabaugh, Claude Tardif, David Wehlau
We investigate a correspondence between the complexity hierarchy of constraint satisfaction problems and a hierarchy of logical compactness hypotheses for finite relational structu…
Hedetniemi's conjecture and adjoint functors in thin categories
Jan Foniok, Claude Tardif
We survey results on Hedetniemi's conjecture which are connected to adjoint functors in the "thin" category of graphs, and expose the obstacles to extending these results.
Topologically -chromatic graphs and signatures of odd cycles
Gord Simons, Claude Tardif, David Wehlau
We investigate group-theoretic "signatures" of odd cycles of a graph, and their connections to topological obstructions to 3-colourability. In the case of signatures derived from f…
Generalised Mycielski graphs and bounds on chromatic numbers
Gord Simons, Claude Tardif, David Wehlau
We prove that the coindex of the box complex of a graph can be measured by the generalised Mycielski graphs which admit a homomorphism to it. As a consequence,…
Homomorphisms of binary Cayley graphs
Laurent Beaudou, Reza Naserasr, Claude Tardif
A binary Cayley graph is a Cayley graph based on a binary group. In 1982, Payan proved that any non-bipartite binary Cayley graph must contain a generalized Mycielski graph of an o…
Adjoint functors in graph theory
Jan Foniok, Claude Tardif
We survey some uses of adjoint functors in graph theory pertaining to colourings, complexity reductions, multiplicativity, circular colourings and tree duality. The exposition of t…
Digraph functors which admit both left and right adjoints
Jan Foniok, Claude Tardif
For our purposes, two functors Λ and Γ are said to be respectively left and right adjoints of each other if for any digraphs G and H, there exists a homomorphism of Λ(G) to H if an…
Regular families of forests, antichains and duality pairs of relational structures
Péter L. Erdős, Dömötör Pálvölgyi, Claude Tardif +1
Homomorphism duality pairs play crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully char…
Caterpillar dualities and regular languages
Péter L. Erdős, Claude Tardif, Gábor Tardos
We characterize obstruction sets in caterpillar dualities in terms of regular languages, and give a construction of the dual of a regular family of caterpillars. We show that these…
On infinite-finite duality pairs of directed graphs
Péter L. Erdős, Claude Tardif, Gábor Tardos
The (A,D) duality pairs play crucial role in the theory of general relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully…
Dualities and dual pairs in Heyting algebras
Jan Foniok, Jaroslav Nesetril, Ales Pultr +1
We extract the abstract core of finite homomorphism dualities using the techniques of Heyting algebras and (combinatorial) categories.
Interleaved adjoints on directed graphs
Jan Foniok, Jaroslav Nesetril, Claude Tardif
For an integer k >= 1, the k-th interlacing adjoint of a digraph G is the digraph i_k(G) with vertex-set V(G)^k, and arcs ((u_1, ..., u_k), (v_1, ..., v_k)) such that (u_i,v_i) \in…
Adjoint functors and tree duality
Jan Foniok, Claude Tardif
A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existenc…
A Characterisation of First-Order Constraint Satisfaction Problems
Benoit Larose, Cynthia Loten, Claude Tardif
We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is dec…