HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Software for testing graph homomorphism

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
homomorphismgraphtestingforsoftware

Problem

I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to test graph homomorphism from $G$ to $H$?

Solution

The best way (in terms of laziness) is to use the freely available tool Sage which has the best support for graph theory.

Example

sage: G = graphs.PetersenGraph()
sage: G.has_homomorphism_to(graphs.CycleGraph(5))
False
sage: G.has_homomorphism_to(graphs.CompleteGraph(5))
{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}

Code Snippets

sage: G = graphs.PetersenGraph()
sage: G.has_homomorphism_to(graphs.CycleGraph(5))
False
sage: G.has_homomorphism_to(graphs.CompleteGraph(5))
{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}

Context

StackExchange Computer Science Q#16375, answer score: 8

Revisions (0)

No revisions yet.