Related Research Articles
Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:
In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.
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.
In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.
Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.
András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.
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 (1951), after whom it is named.
In the mathematical theory of infinite graphs, the Erdős–Dushnik–Miller theorem is a form of Ramsey's theorem stating that every infinite graph contains either a countably infinite independent set, or a clique with the same cardinality as the whole graph.
In graph theory, a Trémaux tree of an undirected graph is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.
In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.
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.
In graph theory, the Henson graphGi is an undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all Ki-free finite graphs as induced subgraphs. For instance, G3 is a triangle-free graph that contains all finite triangle-free graphs.
In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.
In theoretical computer science and metric geometry, the GNRS conjecture connects the theory of graph minors, the stretch factor of embeddings, and the approximation ratio of multi-commodity flow problems. It is named after Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair, who formulated it in 2004.
In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.
In graph theory, there are two related properties of a hypergraph that are called its "width". Given a hypergraph H =, we say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K. Then:
In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.
References
- 1 2 3 DeVos, Matthew (October 22, 2007), "Unfriendly partitions", Open problem garden
- ↑ Shelah, Saharon; Milner, E. C. (1990), "Graphs with no unfriendly partitions" (PDF), in Baker, A.; Bollobás, B.; Hajnal, A. (eds.), A tribute to Paul Erdős, Cambridge University Press, pp. 373–384, doi:10.1177/016502549001300309, MR 1117030
- ↑ Aharoni, R.; Milner, E. C.; Prikry, K. (1990), "Unfriendly partitions of a graph", Journal of Combinatorial Theory, Series B, 50 (1): 1–10, doi: 10.1016/0095-8956(90)90092-E , MR 1070461
- ↑ Bruhn, Henning; Diestel, Reinhard; Georgakopoulos, Agelos; Sprüssel, Philipp (2010), "Every rayless graph has an unfriendly partition", Combinatorica, 30 (5): 521–532, doi:10.1007/s00493-010-2590-3, MR 2776717
- ↑ Berger, Eli (2017), "Unfriendly partitions for graphs not containing a subdivision of an infinite clique", Combinatorica, 37 (2): 157–166, doi:10.1007/s00493-015-3261-1, MR 3638340