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 automorphismrelated functions to "Automorphisms.mac".

Though graph colouring is a special case, it deserves a separate module (Graphs/Lisp/Colouring).
 Todo:
 Bruteforce 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 subgroup.

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_graphfunction, but this options seems to have no effect. A bug? Ask on the Maxima mailing list!

For the Petersengraph apparently draw_graph has a fixed builtin drawing, and vertexlabels 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 Hcoloring, 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 NPcomplete.

That is, for the NPcompleteness result implement the reductions, and for the polytime 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.