Related Research Articles
Tomaž (Tomo) Pisanski is a Slovenian mathematician working mainly in discrete mathematics and graph theory. He is considered by many Slovenian mathematicians to be the "father of Slovenian discrete mathematics."
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.
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.
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 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 mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color.
In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic numberA(G) of a graph G is the fewest colors needed in any acyclic coloring of G.
In combinatorics, the Dinitz theorem is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin.
In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is a proper edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.
In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.
In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u1, u2, …, un} and {v1, v2, …, vn} and with an edge from ui to vj whenever i ≠ j.
In combinatorial mathematics, a Latin rectangle is an r × n matrix, using n symbols, usually the numbers 1, 2, 3, ..., n or 0, 1, ..., n − 1 as its entries, with no number occurring more than once in any row or column.
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.
Adam Wade Marcus is an American mathematician. He held the Chair of Combinatorial Analysis in the Institute of Mathematics at the École Polytechnique Fédérale de Lausanne until February 2023. The team of Marcus, Daniel Spielman and Nikhil Srivastava was awarded the Pólya Prize in 2014 for their resolution of the Kadison–Singer problem and later the Michael and Sheila Held Prize in 2021 for their solution to long-standing conjectures in the study of Ramanujan graphs.
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.
In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices.
Ian Murray Wanless is a professor in the School of Mathematics at Monash University in Melbourne, Australia. His research area is combinatorics, principally Latin squares, graph theory and matrix permanents.
Kristina L. Vušković is a Serbian mathematician and theoretical computer scientist working in graph theory. She is Professor in Algorithms and Combinatorics in the School of Computing at the University of Leeds, and a professor of computer science at Union University (Serbia).
Debra Lynn Boutin is an American mathematician, the Samuel F. Pratt Professor of Mathematics at Hamilton College, where she chairs the mathematics department. Her research involves the symmetries of graphs and distinguishing colorings of graphs.
References
- 1 2 New Department Chair, Dalhousie Department of Mathematics and Statistics, 1 July 2016, retrieved 2021-01-13
- 1 2 Activity Group on Discrete Mathematics, Society for Industrial and Applied Mathematics, retrieved 2021-01-13
- 1 2 3 Curriculum vitae (PDF), retrieved 2021-01-13
- ↑ Jeannette Janssen at the Mathematics Genealogy Project
- ↑ Board of directors, Atlantic Association for Research in the Mathematical Sciences, retrieved 2021-01-13
- ↑ Cipra, Barry (1994), What's Happening in the Mathematical Sciences, vol. 2, American Mathematical Society, p. 43, ISBN 9780821889985
- ↑ Dinitz, Jeffrey H. (1995), Review of "The list chromatic index of a bipartite multigraph" by Fred Galvin, MR 1309363
