Graph homomorphism

Last updated

A homomorphism from the flower snark J5 into the cycle graph C5.
It is also a retraction onto the subgraph on the central five vertices. Thus J5 is in fact homomorphically equivalent to the core C5. Graph homomorphism into C5.svg
A homomorphism from the flower snark J5 into the cycle graph C5.
It is also a retraction onto the subgraph on the central five vertices. Thus J5 is in fact homo­mor­phi­cally equivalent to the core C5.

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.

Contents

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. [1] The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a category (one for undirected graphs and one for directed graphs). [2] 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. [3]

Definitions

In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed. A graph homomorphism [4] f  from a graph to a graph , written

f : GH

is a function from to that preserves edges. 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

GH .

The above definition is extended to directed graphs. Then, for a homomorphism f : GH, (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 maps distinct vertices in G to distinct vertices in H) if and only if G is isomorphic to a subgraph of H. If a homomorphism f : GH is a bijection, and its inverse function f −1 is also a graph homomorphism, then f is a graph isomorphism. [5]

Covering maps are a special kind of homomorphisms that mirror the definition and many properties of covering maps in topology. [6] They are defined as surjective homomorphisms (i.e., something maps to each vertex) that are also locally bijective, that is, a bijection on the neighbourhood of each vertex. An example is the bipartite double cover, formed from a graph by splitting each vertex v into v0 and v1 and replacing each edge u,v with edges u0,v1 and v0,u1. The function mapping v0 and v1 in the cover to v in the original graph is a homomorphism and a covering map.

Graph homeomorphism is a different notion, not related directly to homomorphisms. Roughly speaking, it requires injectivity, but allows mapping edges to paths (not just to edges). Graph minors are a still more relaxed notion.

Cores and retracts

K7, the complete graph with 7 vertices, is a core. Complete graph K7.svg
K7, the complete graph with 7 vertices, is a core.

Two graphs G and H are homomorphically equivalent if GH and HG. [4] The maps are not necessarily surjective nor injective. For instance, the complete bipartite graphs K2,2 and K3,3 are homomorphically equivalent: each map can be defined as taking the left (resp. right) half of the domain graph and mapping to just one vertex in the left (resp. right) half of the image graph.

A retraction is a homomorphism r from a graph G to a subgraph H of G such that r(v) = v for each vertex v of H. In this case the subgraph H is called a retract of G. [7]

A core is a graph with no homomorphism to any proper subgraph. Equivalently, a core can be defined as a graph that does not retract to any proper subgraph. [8] Every graph G is homomorphically equivalent to a unique core (up to isomorphism), called the core of G. [9] Notably, this is not true in general for infinite graphs. [10] However, the same definitions apply to directed graphs and a directed graph is also equivalent to a unique core. Every graph and every directed graph contains its core as a retract and as an induced subgraph. [7]

For example, all complete graphs Kn and all odd cycles (cycle graphs of odd length) are cores. Every 3-colorable graph G that contains a triangle (that is, has the complete graph K3 as a subgraph) is homomorphically equivalent to K3. This is because, on one hand, a 3-coloring of G is the same as a homomorphism GK3, as explained below. On the other hand, every subgraph of G trivially admits a homomorphism into G, implying K3G. This also means that K3 is the core of any such graph G. Similarly, every bipartite graph that has at least one edge is equivalent to K2. [11]

Connection to colorings

A k-coloring, for some integer k, is an assignment of one of k colors to each vertex of a graph G such that the endpoints of each edge get different colors. The k-colorings of G correspond exactly to homomorphisms from G to the complete graph Kk. [12] Indeed, the vertices of Kk correspond to the k colors, and two colors are adjacent as vertices of Kk if and only if they are different. Hence a function defines a homomorphism to Kk if and only if it maps adjacent vertices of G to different colors (i.e., it is a k-coloring). In particular, G is k-colorable if and only if it is Kk-colorable. [12]

If there are two homomorphisms GH and HKk, then their composition GKk is also a homomorphism. [13] In other words, if a graph H can be colored with k colors, and there is a homomorphism from G to H, then G can also be k-colored. Therefore, GH implies χ(G) ≤ χ(H), where χ denotes the chromatic number of a graph (the least k for which it is k-colorable). [14]

Variants

General homomorphisms can also be thought of as a kind of coloring: if the vertices of a fixed graph H are the available colors and edges of H describe which colors are compatible, then an H-coloring of G is an assignment of colors to vertices of G such that adjacent vertices get compatible colors. Many notions of graph coloring fit into this pattern and can be expressed as graph homomorphisms into different families of graphs. Circular colorings can be defined using homomorphisms into circular complete graphs, refining the usual notion of colorings. [15] Fractional and b-fold coloring can be defined using homomorphisms into Kneser graphs. [16] T-colorings correspond to homomorphisms into certain infinite graphs. [17] An oriented coloring of a directed graph is a homomorphism into any oriented graph. [18] An L(2,1)-coloring is a homomorphism into the complement of the path graph that is locally injective, meaning it is required to be injective on the neighbourhood of every vertex. [19]

Orientations without long paths

Another interesting connection concerns orientations of graphs. An orientation of an undirected graph G is any directed graph obtained by choosing one of the two possible orientations for each edge. An example of an orientation of the complete graph Kk is the transitive tournament Tk with vertices 1,2,…,k and arcs from i to j whenever i < j. A homomorphism between orientations of graphs G and H yields a homomorphism between the undirected graphs G and H, simply by disregarding the orientations. On the other hand, given a homomorphism GH between undirected graphs, any orientation H of H can be pulled back to an orientation G of G so that G has a homomorphism to H. Therefore, a graph G is k-colorable (has a homomorphism to Kk) if and only if some orientation of G has a homomorphism to Tk. [20]

A folklore theorem states that for all k, a directed graph G has a homomorphism to Tk if and only if it admits no homomorphism from the directed path Pk+1. [21] Here Pn is the directed graph with vertices 1, 2, …, n and edges from i to i + 1, for i = 1, 2, …, n − 1. Therefore, a graph is k-colorable if and only if it has an orientation that admits no homomorphism from Pk+1. This statement can be strengthened slightly to say that a graph is k-colorable if and only if some orientation contains no directed path of length k (no Pk+1 as a subgraph). This is the Gallai–Hasse–Roy–Vitaver theorem.

Connection to constraint satisfaction problems

Examples

Graph H of non-consecutive weekdays, isomorphic to the complement graph of C7 and to the circular clique K7/2 Graph of non-adjacent weekdays.svg
Graph H of non-consecutive weekdays, isomorphic to the complement graph of C7 and to the circular clique K7/2

Some scheduling problems can be modeled as a question about finding graph homomorphisms. [22] [23] As an example, one might want to assign workshop courses to time slots in a calendar so that two courses attended by the same student are not too close to each other in time. The courses form a graph G, with an edge between any two courses that are attended by some common student. The time slots form a graph H, with an edge between any two slots that are distant enough in time. For instance, if one wants a cyclical, weekly schedule, such that each student gets their workshop courses on non-consecutive days, then H would be the complement graph of C7. A graph homomorphism from G to H is then a schedule assigning courses to time slots, as specified. [22] To add a requirement saying that, e.g., no single student has courses on both Friday and Monday, it suffices to remove the corresponding edge from H.

A simple frequency allocation problem can be specified as follows: a number of transmitters in a wireless network must choose a frequency channel on which they will transmit data. To avoid interference, transmitters that are geographically close should use channels with frequencies that are far apart. If this condition is approximated with a single threshold to define 'geographically close' and 'far apart', then a valid channel choice again corresponds to a graph homomorphism. It should go from the graph of transmitters G, with edges between pairs that are geographically close, to the graph of channels H, with edges between channels that are far apart. While this model is rather simplified, it does admit some flexibility: transmitter pairs that are not close but could interfere because of geographical features can be added to the edges of G. Those that do not communicate at the same time can be removed from it. Similarly, channel pairs that are far apart but exhibit harmonic interference can be removed from the edge set of H. [24]

In each case, these simplified models display many of the issues that have to be handled in practice. [25] Constraint satisfaction problems, which generalize graph homomorphism problems, can express various additional types of conditions (such as individual preferences, or bounds on the number of coinciding assignments). This allows the models to be made more realistic and practical.

Formal view

Graphs and directed graphs can be viewed as a special case of the far more general notion called relational structures (defined as a set with a tuple of relations on it). Directed graphs are structures with a single binary relation (adjacency) on the domain (the vertex set). [26] [3] Under this view, homomorphisms of such structures are exactly graph homomorphisms. In general, the question of finding a homomorphism from one relational structure to another is a constraint satisfaction problem (CSP). The case of graphs gives a concrete first step that helps to understand more complicated CSPs. Many algorithmic methods for finding graph homomorphisms, like backtracking, constraint propagation and local search, apply to all CSPs. [3]

For graphs G and H, the question of whether G has a homomorphism to H corresponds to a CSP instance with only one kind of constraint, [3] as follows. The variables are the vertices of G and the domain for each variable is the vertex set of H. An evaluation is a function that assigns to each variable an element of the domain, so a function f from V(G) to V(H). Each edge or arc (u,v) of G then corresponds to the constraint ((u,v), E(H)). This is a constraint expressing that the evaluation should map the arc (u,v) to a pair (f(u),f(v)) that is in the relation E(H), that is, to an arc of H. A solution to the CSP is an evaluation that respects all constraints, so it is exactly a homomorphism from G to H.

Structure of homomorphisms

Compositions of homomorphisms are homomorphisms. [13] In particular, the relation → on graphs is transitive (and reflexive, trivially), so it is a preorder on graphs. [27] Let the equivalence class of a graph G under homomorphic equivalence be [G]. The equivalence class can also be represented by the unique core in [G]. The relation → is a partial order on those equivalence classes; it defines a poset. [28]

Let G < H denote that there is a homomorphism from G to H, but no homomorphism from H to G. The relation → is a dense order, meaning that for all (undirected) graphs G, H such that G < H, there is a graph K such that G < K < H (this holds except for the trivial cases G = K0 or K1). [29] [30] For example, between any two complete graphs (except K0, K1, K2) there are infinitely many circular complete graphs, corresponding to rational numbers between natural numbers. [31]

The poset of equivalence classes of graphs under homomorphisms is a distributive lattice, with the join of [G] and [H] defined as (the equivalence class of) the disjoint union [GH], and the meet of [G] and [H] defined as the tensor product [G × H] (the choice of graphs G and H representing the equivalence classes [G] and [H] does not matter). [32] The join-irreducible elements of this lattice are exactly connected graphs. This can be shown using the fact that a homomorphism maps a connected graph into one connected component of the target graph. [33] [34] The meet-irreducible elements of this lattice are exactly the multiplicative graphs. These are the graphs K such that a product G × H has a homomorphism to K only when one of G or H also does. Identifying multiplicative graphs lies at the heart of Hedetniemi's conjecture. [35] [36]

Graph homomorphisms also form a category, with graphs as objects and homomorphisms as arrows. [37] The initial object is the empty graph, while the terminal object is the graph with one vertex and one loop at that vertex. The tensor product of graphs is the category-theoretic product and the exponential graph is the exponential object for this category. [36] [38] Since these two operations are always defined, the category of graphs is a cartesian closed category. For the same reason, the lattice of equivalence classes of graphs under homomorphisms is in fact a Heyting algebra. [36] [38]

For directed graphs the same definitions apply. In particular → is a partial order on equivalence classes of directed graphs. It is distinct from the order → on equivalence classes of undirected graphs, but contains it as a suborder. This is because every undirected graph can be thought of as a directed graph where every arc (u,v) appears together with its inverse arc (v,u), and this does not change the definition of homomorphism. The order → for directed graphs is again a distributive lattice and a Heyting algebra, with join and meet operations defined as before. However, it is not dense. There is also a category with directed graphs as objects and homomorphisms as arrows, which is again a cartesian closed category. [39] [38]

Incomparable graphs

The Grotzsch graph, incomparable to K3 Groetzsch-graph.svg
The Grötzsch graph, incomparable to K3

There are many incomparable graphs with respect to the homomorphism preorder, that is, pairs of graphs such that neither admits a homomorphism into the other. [40] One way to construct them is to consider the odd girth of a graph G, the length of its shortest odd-length cycle. The odd girth is, equivalently, the smallest odd number g for which there exists a homomorphism from the cycle graph on g vertices to G. For this reason, if GH, then the odd girth of G is greater than or equal to the odd girth of H. [41]

On the other hand, if GH, then the chromatic number of G is less than or equal to the chromatic number of H. Therefore, if G has strictly larger odd girth than H and strictly larger chromatic number than H, then G and H are incomparable. [40] For example, the Grötzsch graph is 4-chromatic and triangle-free (it has girth 4 and odd girth 5), [42] so it is incomparable to the triangle graph K3.

Examples of graphs with arbitrarily large values of odd girth and chromatic number are Kneser graphs [43] and generalized Mycielskians. [44] A sequence of such graphs, with simultaneously increasing values of both parameters, gives infinitely many incomparable graphs (an antichain in the homomorphism preorder). [45] Other properties, such as density of the homomorphism preorder, can be proved using such families. [46] Constructions of graphs with large values of chromatic number and girth, not just odd girth, are also possible, but more complicated (see Girth and graph coloring).

Among directed graphs, it is much easier to find incomparable pairs. For example, consider the directed cycle graphs Cn, with vertices 1, 2, …, n and edges from i to i + 1 (for i = 1, 2, …, n − 1) and from n to 1. There is a homomorphism from Cn to Ck (n, k ≥ 3) if and only if n is a multiple of k. In particular, directed cycle graphs Cn with n prime are all incomparable. [47]

Computational complexity

In the graph homomorphism problem, an instance is a pair of graphs (G,H) and a solution is a homomorphism from G to H. The general decision problem, asking whether there is any solution, is NP-complete. [48] However, limiting allowed instances gives rise to a variety of different problems, some of which are much easier to solve. Methods that apply when restraining the left side G are very different than for the right side H, but in each case a dichotomy (a sharp boundary between easy and hard cases) is known or conjectured.

Homomorphisms to a fixed graph

The homomorphism problem with a fixed graph H on the right side of each instance is also called the H-coloring problem. When H is the complete graph Kk, this is the graph k-coloring problem, which is solvable in polynomial time for k = 0, 1, 2, and NP-complete otherwise. [49] In particular, K2-colorability of a graph G is equivalent to G being bipartite, which can be tested in linear time. More generally, whenever H is a bipartite graph, H-colorability is equivalent to K2-colorability (or K0 / K1-colorability when H is empty/edgeless), hence equally easy to decide. [50] Pavol Hell and Jaroslav Nešetřil proved that, for undirected graphs, no other case is tractable:

Hell–Nešetřil theorem (1990): The H-coloring problem is in P when H is bipartite and NP-complete otherwise. [51] [52]

This is also known as the dichotomy theorem for (undirected) graph homomorphisms, since it divides H-coloring problems into NP-complete or P problems, with no intermediate cases. For directed graphs, the situation is more complicated and in fact equivalent to the much more general question of characterizing the complexity of constraint satisfaction problems. [53] It turns out that H-coloring problems for directed graphs are just as general and as diverse as CSPs with any other kinds of constraints. [54] [55] Formally, a (finite) constraint language (or template) Γ is a finite domain and a finite set of relations over this domain. CSP(Γ) is the constraint satisfaction problem where instances are only allowed to use constraints in Γ.

Theorem (Feder, Vardi 1998): For every constraint language Γ, the problem CSP(Γ) is equivalent under polynomial-time reductions to some H-coloring problem, for some directed graph H. [55]

Intuitively, this means that every algorithmic technique or complexity result that applies to H-coloring problems for directed graphs H applies just as well to general CSPs. In particular, one can ask whether the Hell–Nešetřil theorem can be extended to directed graphs. By the above theorem, this is equivalent to the Feder–Vardi conjecture (aka CSP conjecture, dichotomy conjecture) on CSP dichotomy, which states that for every constraint language Γ, CSP(Γ) is NP-complete or in P. [48] This conjecture was proved in 2017 independently by Dmitry Zhuk and Andrei Bulatov, leading to the following corollary:

Corollary (Bulatov 2017; Zhuk 2017): The H-coloring problem on directed graphs, for a fixed H, is either in P or NP-complete.

Homomorphisms from a fixed family of graphs

The homomorphism problem with a single fixed graph G on left side of input instances can be solved by brute-force in time |V(H)|O(|V(G)|), so polynomial in the size of the input graph H. [56] In other words, the problem is trivially in P for graphs G of bounded size. The interesting question is then what other properties of G, beside size, make polynomial algorithms possible.

The crucial property turns out to be treewidth, a measure of how tree-like the graph is. For a graph G of treewidth at most k and a graph H, the homomorphism problem can be solved in time |V(H)|O(k) with a standard dynamic programming approach. In fact, it is enough to assume that the core of G has treewidth at most k. This holds even if the core is not known. [57] [58]

The exponent in the |V(H)|O(k)-time algorithm cannot be lowered significantly: no algorithm with running time |V(H)|o(tw(G) /log tw(G)) exists, assuming the exponential time hypothesis (ETH), even if the inputs are restricted to any class of graphs of unbounded treewidth. [59] The ETH is an unproven assumption similar to P ≠ NP, but stronger. Under the same assumption, there are also essentially no other properties that can be used to get polynomial time algorithms. This is formalized as follows:

Theorem (Grohe): For a computable class of graphs , the homomorphism problem for instances with is in P if and only if graphs in have cores of bounded treewidth (assuming ETH). [58]

One can ask whether the problem is at least solvable in a time arbitrarily highly dependent on G, but with a fixed polynomial dependency on the size of H. The answer is again positive if we limit G to a class of graphs with cores of bounded treewidth, and negative for every other class. [58] In the language of parameterized complexity, this formally states that the homomorphism problem in parameterized by the size (number of edges) of G exhibits a dichotomy. It is fixed-parameter tractable if graphs in have cores of bounded treewidth, and W[1]-complete otherwise.

The same statements hold more generally for constraint satisfaction problems (or for relational structures, in other words). The only assumption needed is that constraints can involve only a bounded number of variables (all relations are of some bounded arity, 2 in the case of graphs). The relevant parameter is then the treewidth of the primal constraint graph. [59]

See also

Notes

  1. Hell & Nešetřil 2004, p. 27.
  2. Hell & Nešetřil 2004, p. 109.
  3. 1 2 3 4 Hell & Nešetřil 2008.
  4. 1 2 For introductions, see (in order of increasing length): Cameron (2006); Hahn & Tardif (1997); Hell & Nešetřil (2004).
  5. Hahn & Tardif 1997, Observation 2.3.
  6. Godsil & Royle 2001, p. 115.
  7. 1 2 Hell & Nešetřil 2004, p. 19.
  8. Hell & Nešetřil 2004, Proposition 1.31.
  9. Cameron 2006, Proposition 2.3; Hell & Nešetřil 2004, Corollary 1.32.
  10. Hell & Nešetřil 2004, p. 34.
  11. Cameron 2006, p. 4, Proposition 2.5.
  12. 1 2 Cameron 2006, p. 1; Hell & Nešetřil 2004, Proposition 1.7.
  13. 1 2 Hell & Nešetřil 2004, §1.7.
  14. Hell & Nešetřil 2004, Corollary 1.8.
  15. Hell & Nešetřil 2004, §6.1; Hahn & Tardif 1997, §4.4.
  16. Hell & Nešetřil 2004, §6.2; Hahn & Tardif 1997, §4.5.
  17. Hell & Nešetřil 2004, §6.3.
  18. Hell & Nešetřil 2004, §6.4.
  19. Fiala, J.; Kratochvíl, J. (2002), "Partial covers of graphs", Discussiones Mathematicae Graph Theory, 22 (1): 89–99, doi:10.7151/dmgt.1159, S2CID   17507393
  20. Hell & Nešetřil 2004, pp. 13–14.
  21. Hell & Nešetřil 2004, Proposition 1.20.
  22. 1 2 Cameron 2006, p. 1.
  23. Hell & Nešetřil 2004, §1.8.
  24. Hell & Nešetřil 2004, pp. 30–31.
  25. Hell & Nešetřil 2004, pp. 31–32.
  26. Hell & Nešetřil 2004 , p. 28, note relational structures are called relational systems there.
  27. Hell & Nešetřil 2004, §3.1.
  28. Hell & Nešetřil 2004, Theorem 3.1.
  29. Hell & Nešetřil 2004, Theorem 3.30; Hahn & Tardif 1997, Theorem 2.33.
  30. Welzl, E. (1982), "Color-families are dense", Theoretical Computer Science , 17: 29–41, doi: 10.1016/0304-3975(82)90129-3
  31. Hell & Nešetřil 2004, p. 192; Hahn & Tardif 1997, p. 127.
  32. Hell & Nešetřil 2004 , Proposition 3.2, distributivity is stated in Proposition 2.4; Hahn & Tardif 1997 , Theorem 2.37.
  33. Kwuida, Léonard; Lehtonen, Erkko (2011), "On the Homomorphism Order of Labeled Posets", Order , 28 (2): 251–265, arXiv: 0911.0200 , doi:10.1007/s11083-010-9169-x, S2CID   14920600
  34. Gray 2014, Lemma 3.7.
  35. Tardif, C. (2008), "Hedetniemi's conjecture, 40 years later" (PDF), Graph Theory Notes of New York, 54: 46–57, MR   2445666, archived from the original (PDF) on 2021-07-12, retrieved 2017-08-05.
  36. 1 2 3 Dwight, D.; Sauer, N. (1996), "Lattices arising in categorial investigations of Hedetniemi's conjecture", Discrete Mathematics , 152 (1–3): 125–139, doi: 10.1016/0012-365X(94)00298-W
  37. Hell & Nešetřil 2004, p. 125.
  38. 1 2 3 Gray 2014.
  39. Brown et al. 2008.
  40. 1 2 Hell & Nešetřil 2004, p. 7.
  41. Hahn & Tardif 1997, Observation 2.6.
  42. Weisstein, Eric W., "Grötzsch Graph", MathWorld
  43. Hahn & Tardif 1997, Proposition 3.14.
  44. Gyárfás, A.; Jensen, T.; Stiebitz, M. (2004), "On Graphs With Strongly Independent Color-Classes", Journal of Graph Theory , 46 (1): 1–14, doi:10.1002/jgt.10165, S2CID   17859655
  45. Hell & Nešetřil 2004, Proposition 3.4.
  46. Hell & Nešetřil 2004, p. 96.
  47. Hell & Nešetřil 2004, p. 35.
  48. 1 2 Bodirsky 2007, §1.3.
  49. Hell & Nešetřil 2004, §5.1.
  50. Hell & Nešetřil 2004, Proposition 5.1.
  51. Hell & Nešetřil 2004, §5.2.
  52. Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory , Series B, 48 (1): 92–110, doi: 10.1016/0095-8956(90)90132-J
  53. Hell & Nešetřil 2004, §5.3.
  54. Hell & Nešetřil 2004, Theorem 5.14.
  55. 1 2 Feder, Tomás; Vardi, Moshe Y. (1998), "The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory", SIAM Journal on Computing , 28 (1): 57–104, doi:10.1137/S0097539794266766
  56. Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socala, Arkadiusz (2016), "Tight bounds for graph homomorphism and subgraph isomorphism", in Krauthgamer, Robert (ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016, Society for Industrial and Applied Mathematics, pp. 1643–1649, arXiv: 1507.03738 , doi:10.1137/1.9781611974331.ch112, ISBN   978-1-611974-33-1
  57. Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y. (2002), "Constraint satisfaction, bounded treewidth, and finite-variable logics", in Van Hentenryck, Pascal (ed.), Principles and Practice of Constraint Programming – CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9–13, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2470, Springer, pp. 310–326, doi:10.1007/3-540-46135-3_21, ISBN   978-3-540-44120-5
  58. 1 2 3 Grohe, Martin (2007), "The complexity of homomorphism and constraint satisfaction problems seen from the other side", Journal of the ACM , 54 (1): 1–es, doi:10.1145/1206035.1206036, S2CID   11797906
  59. 1 2 Marx, Dániel (2010), "Can You Beat Treewidth?", Theory of Computing , 6: 85–112, doi: 10.4086/toc.2010.v006a005

Related Research Articles

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

<span class="mw-page-title-main">Graph coloring</span> Methodic assignment of colors to elements of a graph

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

<span class="mw-page-title-main">Extremal graph theory</span>

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Connectivity (graph theory)</span> Basic concept of graph theory

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of vertices in that subset.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Hadwiger number</span> Size of largest complete graph made by contracting edges of a given graph

In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G. Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.

In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit–evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs.

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 Jan Mycielski. 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.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.

In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for Leon Mirsky and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai–Hasse–Roy–Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős–Szekeres theorem on monotonic subsequences.

<span class="mw-page-title-main">Gallai–Hasse–Roy–Vitaver theorem</span> Duality of graph colorings and orientations

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph equals one plus the length of a longest path in an orientation of chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

References

General books and expositions

In constraint satisfaction and universal algebra

In lattice theory and category theory