Related Research Articles
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.
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, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k − 1 independent sets.
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.
In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords. The chords may be uncrossed or they may cross each other, as long as there are at least two of them.
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.
George Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University.
Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He 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.
The Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. Series A is concerned primarily with structures, designs, and applications of combinatorics. Series B is concerned primarily with graph and matroid theory. The two series are two of the leading journals in the field and are widely known as JCTA and JCTB.
In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G.
Zoltán Füredi is a Hungarian mathematician, working in combinatorics, mainly in discrete geometry and extremal combinatorics. He was a student of Gyula O. H. Katona. He is a corresponding member of the Hungarian Academy of Sciences (2004). He is a research professor of the Rényi Mathematical Institute of the Hungarian Academy of Sciences, and a professor at the University of Illinois Urbana-Champaign (UIUC).
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.
In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor at Smith College, who stated it as a conjecture in 2007; it is one of his many conjectures in graph coloring theory. The conjecture states that, among all graphs requiring colors, the complete graph is the one with the smallest crossing number. Equivalently, if a graph can be drawn with fewer crossings than , then, according to the conjecture, it may be colored with fewer than colors.
Norman Linstead Biggs is a leading British mathematician focusing on discrete mathematics and in particular algebraic combinatorics.
Paul Allen Catlin was a mathematician, professor of mathematics who worked in graph theory and number theory. He wrote a significant paper on the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.
In graph theory, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979. A proof was announced in 2016, and published in four papers in 2020.
In graph theory, a -bounded family of graphs is one for which there is some function such that, for every integer the graphs in with can be colored with at most colors. The function is called a -binding function for . These concepts and their notations were formulated by András Gyárfás. The use of the Greek letter chi in the term -bounded is based on the fact that the chromatic number of a graph is commonly denoted . An overview of the area can be found in a survey of Alex Scott and Paul Seymour.
References
- 1 2 Baker, Matthew (January 2018). "Hodge theory in combinatorics". Bulletin of the American Mathematical Society. 55 (1): 57–80. arXiv: 1705.07960 . doi: 10.1090/bull/1599 . ISSN 0273-0979. S2CID 51813455.
- ↑ R. C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52–71. MR0224505 (37:104)
- ↑ Hoggar, S. G (1974-06-01). "Chromatic polynomials and logarithmic concavity". Journal of Combinatorial Theory . Series B. 16 (3): 248–254. doi: 10.1016/0095-8956(74)90071-9 . ISSN 0095-8956.
- ↑ Huh, June. "Hard Lefschetz theorem and Hodge-Riemann relations for combinatorial geometries" (PDF).
- ↑ "He Dropped Out to Become a Poet. Now He's Won a Fields Medal". Quanta Magazine . 5 July 2022. Retrieved 5 July 2022.
- ↑ Kalai, Gil (July 2022). "The Work of June Huh" (PDF). Proceedings of the International Congress of Mathematicians 2022: 1–16., pp. 2–4.
- ↑ Huh, June (2012). "Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs". Journal of the American Mathematical Society. 25 (3): 907–927. arXiv: 1008.4749 . doi: 10.1090/S0894-0347-2012-00731-0 .
 | This graph theory-related article is a stub. You can help Wikipedia by expanding it. |