Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Graph homomorphism
Summary
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.
Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.
The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a (one for undirected graphs and one for directed graphs).
The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time. Boundaries between tractable and intractable cases have been an active area of research.
In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed.
A graph homomorphism f from a graph to a graph , written
f : G → H
is a function from to that maps endpoints of each edge in to endpoints of an edge in . Formally, implies , for all pairs of vertices in .
If there exists any homomorphism from G to H, then G is said to be homomorphic to H or H-colorable. This is often denoted as just
G → H .
The above definition is extended to directed graphs. Then, for a homomorphism f : G → H, (f(u),f(v)) is an arc (directed edge) of H whenever (u,v) is an arc of G.
There is an injective homomorphism from G to H (i.e., one that never maps distinct vertices to one vertex) if and only if G is a subgraph of H.
If a homomorphism f : G → H is a bijection (a one-to-one correspondence between vertices of G and H) whose inverse function is also a graph homomorphism, then f is a graph isomorphism.
Covering maps are a special kind of homomorphisms that mirror the definition and many properties of covering maps in topology.
They are defined as surjective homomorphisms (i.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (5)
PHYS-512: Statistical physics of computation
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
COM-406: Foundations of Data Science
We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an
CS-250: Algorithms I
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Related lectures (33)
Exponential Family
Covers the concept of the exponential family and discusses forward and backward maps, expensive computations, parameters, functions, and convexity.
Probabilistic Methods in Combinatorics
Covers probabilistic methods in combinatorics, monochromatic edges, 2-colorable graphs, and good 2-colorings.
Information Theory: Basics
Covers the basics of information theory, entropy, and fixed points in graph colorings and the Ising model.
Related publications (74)
The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.
We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...
Elsevier2024Related people (18)
Related units (1)
Related concepts (13)
Tensor product of graphs
In graph theory, the tensor product G × H of graphs G and H is a graph such that the vertex set of G × H is the Cartesian product V(G) × V(H); and vertices (g,h) and math|(''g,h' ) are adjacent in G × H if and only if g is adjacent to g' in G, and h is adjacent to h' in H. The tensor product is also called the direct product, Kronecker product, categorical product, cardinal product, relational product, weak direct product, or conjunction'''.
Complexity of constraint satisfaction
The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains. Solving a constraint satisfaction problem on a finite domain is an NP-complete problem in general. Research has shown a number of polynomial-time subcases, mostly obtained by restricting either the allowed domains or constraints or the way constraints can be placed over the variables.
Mycielskian
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number. Let the n vertices of the given graph G be v1, v2, . . . , vn.