OKlibrary  0.2.1.6
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.

Todo:
Organisation
• 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).
Todo:
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.
Todo:
Handling of automorphism groups
• Given some set of automorphisms, compute the generated sub-group.
• This is better handled in a submodule Algebra/Groups/Permutations.
Todo:
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.
Todo:
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.