65 citations · 87 across the 14 of their papers we have counts for
5 papers · 1 filter
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,…