Homomorphisms.hpp File Reference

Plans regarding graph homomorphisms in general. More...

Go to the source code of this file.

Detailed Description

Plans regarding graph homomorphisms in general.

  • Likely we should move automorphism-related functions to "Automorphisms.mac".
  • Though graph colouring is a special case, it deserves a separate module (Graphs/Lisp/Colouring).
Brute-force automorphism enumeration
  • It would be useful to have the possibility to specify a set of vertices which need to be fixed by the automorphisms.
Handling of automorphism groups
  • Given some set of automorphisms, compute the generated sub-group.
  • This is better handled in a submodule Algebra/Groups/Permutations.
Visualising automorphisms
  • A reasonable visualisaton of an automorphism is to have a second drawing, identical as drawing of an "anonymous" graph, but with the new vertex labels showing the renaming.
  • For this first a drawing needs to be fixed, and then a second one is produced, using the old coordinates and adding just new verttex labels.
  • There is a "redraw"-option for the draw_graph-function, but this options seems to have no effect. A bug? Ask on the Maxima mailing list!
  • For the Petersen-graph apparently draw_graph has a fixed built-in drawing, and vertex-labels can be added (while still showing the same fixed drawing) --- so it should be possible!
  • It would also be needed here to have several gnuplot windows open at the same time --- how to do this?
  • See "Graph drawing" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp.
Deciding whether for given H there is a graph morphism G -> H
  • Implement [Pavol Hell and Jaroslav Nesetril, On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, 1990].
  • If H is bipartite, then (for input G) the problem is decidable in polynomial time (and likely we also find a homomorphism), while otherwise the problem is NP-complete.
  • That is, for the NP-completeness result implement the reductions, and for the poly-time results implement the algorithms.
  • I have seen improved presentations of this result --- do we also have improved algorithms and reductions?

Definition in file Homomorphisms.hpp.