|
Klaus Wagner (mathematician)
Klaus Wagner (March 31, 1910 – February 6, 2000) was a German mathematician known for his contributions to graph theory. Education and career Wagner studied topology at the University of Cologne under the supervision of who had been a student of Issai Schur. Wagner received his Ph.D. in 1937, with a dissertation concerning the Jordan curve theorem and four color theorem, and taught at Cologne for many years himself. In 1970, he moved to the University of Duisburg, where he remained until his retirement in 1978. Graph minors Wagner is known for his contributions to graph theory and particularly the theory of graph minors, graphs that can be formed from a larger graph by contracting and removing edges. Wagner's theorem characterizes the planar graphs as exactly those graphs that do not have as a minor either a complete graph ''K''5 on five vertices or a complete bipartite graph ''K''3,3 with three vertices on each side of its bipartition. That is, these two graphs are the onl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Frank Harary
Frank Harary (March 11, 1921 – January 4, 2005) was an American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory. Harary was a master of clear exposition and, together with his many doctoral students, he standardized the terminology of graphs. He broadened the reach of this field to include physics, psychology, sociology, and even anthropology. Gifted with a keen sense of humor, Harary challenged and entertained audiences at all levels of mathematical sophistication. A particular trick he employed was to turn theorems into games—for instance, students would try to add red edges to a graph on six vertices in order to create a red triangle, while another group of students tried to add edges to create a blue triangle (and each edge of the graph had to be either blue or red). Because of the theorem on friends and strangers, one team or the other would have to win. Biography Frank Harary was born in New Yo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kuratowski's Theorem
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K_5 (the complete graph on five vertices) or of K_ (a complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph). Statement A planar graph is a graph whose vertices can be represented by points in the Euclidean plane, and whose edges can be represented by simple curves in the same plane connecting the points representing their endpoints, such that no two curves intersect except at a common endpoint. Planar graphs are often drawn with straight line segments representing their edges, but by Fáry's theorem this makes no difference to their graph-theoretic characterization. A subdivision of a graph is a graph formed by subdividing its edges into paths of one or mor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Festschrift
In academia, a ''Festschrift'' (; plural, ''Festschriften'' ) is a book honoring a respected person, especially an academic, and presented during their lifetime. It generally takes the form of an edited volume, containing contributions from the honoree's colleagues, former pupils, and friends. ''Festschriften'' are often titled something like ''Essays in Honour of...'' or ''Essays Presented to... .'' Terminology The term, borrowed from German, and literally meaning 'celebration writing' (cognate with ''feast-script''), might be translated as "celebration publication" or "celebratory (piece of) writing". An alternative Latin term is (literally: 'book of friends'). A comparable book presented posthumously is sometimes called a (, 'memorial publication'), but this term is much rarer in English. A ''Festschrift'' compiled and published by electronic means on the internet is called a (pronounced either or ), a term coined by the editors of the late Boris Marshak's , ''Eran ud Aner ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Robertson–Seymour Theorem
In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph ''K''5 or the complete bipartite graph ''K''3,3 as minors. The Robertson–Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004. Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner, although Wagner said he never conjectured it. A weaker result for trees is implied by Kruskal's tree theorem, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Paul Seymour (mathematician)
Paul D. Seymour (born 26 July 1950) is a British mathematician known for his work in discrete mathematics, especially graph theory. He (with others) was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website. Seymour is currently the Albert Baldwin Dod Professor of Mathematics at Princeton University. He won a Sloan Fellowship in 1983, and the Ostrowski Prize in 2004; and (sometimes with others) won the Fulkerson Prize in 1979, 1994, 2006 and 2009, and the Pólya Prize in 1983 and 2004. He received an honorary doctorate from the University of Waterloo in 2008, one from the Technical University of Denmark in 2013, and one from the École normale supérieure de Lyon in 2022. He was an invited ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Neil Robertson (mathematician)
George Neil Robertson (born November 30, 1938) is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University. Education Robertson earned his B.Sc. from Brandon College in 1959, and his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. Biography In 1969, Robertson joined the faculty of the Ohio State University, where he was promoted to Associate Professor in 1972 and Professor in 1984. He was a consultant with Bell Communications Research from 1984 to 1996. He has held visiting faculty positions in many institutions, most extensively at Princeton University from 1996 to 2001, and at Victoria University of Wellington, New Zealand, in 2002. He also holds an adjunct position at King Abdulaziz University in Saudi Arabia.. Research Robertson is known for his work in graph theory, and particularly for a long series of papers co-authored with Paul Seymour and published over a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Forbidden Graph Characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph and the complete bipartite graph . For Kuratowski's theorem, the notion of containment is that of graph homeomorphism, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing (in which case it belongs to the family of planar graphs) or it has a subdivision of at least one of these two graphs as a subgraph (in which case it does not belong to the planar graphs). Definition More generally, a forbidden grap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Isomorphism
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) are adjacent in ''H''. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as G\simeq H. In the case when the bijection is a mapping of a graph onto itself, i.e., when ''G'' and ''H'' are one and the same graph, the bijection is called an automorphism of ''G''. If a graph is finite, we can prove it to be bijective by showing it is one-one/onto; no need to show both. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hadwiger Conjecture (graph Theory)
In graph theory, the Hadwiger conjecture states that if G is loopless and has no K_t 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 more detail, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph K_k on k vertices as a minor This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved. call it "one of the deepest unsolved problems in graph theory." Equivalent forms An equivalent form of the Hadwiger conjecture (the contrapositive of the form stated above ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popularity. Although cliques are most commonly studied during adolescence and middle childhood development, they exist in all age groups. They are often bound together by shared social characteristics such as ethnicity and socioeconomic status. Examples of common or stereotypical adolescent cliques include athletes, nerds, and "outsiders". Typically, people in a clique will not have a completely open friend group and can, therefore, "ban" members if they do something considered unacceptable, such as talking to someone disliked. Some cliques tend to isolate themselves as a group and view themselves as superior to others, which can be demonstrated through bullying and other antisocial behaviors. Terminology Within the concepts of sociology, cliqu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique-sum
In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' each contain cliques of equal size, the clique-sum of ''G'' and ''H'' is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A ''k''-clique-sum is a clique-sum in which both cliques have at most ''k'' vertices. One may also form clique-sums and ''k''-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum operation. Different sources disagree on which edges should be removed as part of a clique-sum operation. In some contexts, such as the decomposition of chordal graphs or strangulated graphs, no edges should be removed. In other contexts, such as the SPQR-tree decomposition of graphs into their 3-vertex-connected components, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Möbius Ladder
In graph theory, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of (the utility graph ), has exactly four-cycles which link together by their shared edges to form a topological Möbius strip. Möbius ladders were named and first studied by . Properties For every even , the Möbius ladder is a nonplanar apex graph, meaning that it cannot be drawn without crossings in the plane but removing one vertex allows the remaining graph to be drawn without crossings. These graphs have crossing number one, and can be embedded without crossings on a torus or projective plane. Thus, they are examples of toroidal graphs. explores embeddings of these graphs onto higher genus surfaces. Möbius ladders are vertex-transitive – they have symmetries taking any vertex to any other vertex – but (with the exceptions of and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
