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 mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.
In graph theory, a branch of mathematics, the left-right planarity test or de Fraysseix–Rosenstiehl planarity criterion is a characterization of planar graphs based on the properties of the depth-first search trees, published by de Fraysseix and Rosenstiehl and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm. In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested.
In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis (1984), following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane. It was proven by Jeremie Chalopin and Daniel Gonçalves (2009).
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.
Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.
In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).
Jaroslav (Jarik) Nešetřil is a Czech mathematician, working at Charles University in Prague. His research areas include combinatorics, graph theory, algebra, posets, computer science.
In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.
The European Journal of Combinatorics is a closed-access peer-reviewed scientific journal for combinatorics. It is an international, bimonthly journal of discrete mathematics, specializing in theories arising from combinatorial problems. The journal is primarily open to papers dealing with mathematical structures within combinatorics and/or establishing direct links between combinatorics and the theories of computing. The journal includes full-length research papers, short notes, and research problems on several topics. This journal has been founded by Michel Deza, Michel Las Vergnas and Pierre Rosenstiehl. The current editor-in-chief is Patrice Ossona de Mendez and the vice editor-in-chief is Marthe Bonamy.
In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by Grünbaum (1973). The star chromatic number of G is the fewest colors needed to star color G.
In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors. According to the four-color theorem, every graph that can be drawn in the plane without edge crossings can have its vertices colored using at most four different colors, so that the two endpoints of every edge have different colors, but according to Grötzsch's theorem only three colors are needed for planar graphs that do not contain three mutually adjacent vertices.
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.
In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph.
In graph theory, a shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter. Shallow minors were introduced by Plotkin, Rao & Smith (1994), who attributed their invention to Charles E. Leiserson and Sivan Toledo.
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.
In the mathematical area of graph theory, a contact graph or tangency graph is a graph whose vertices are represented by geometric objects, and whose edges correspond to two objects touching according to some specified notion. It is similar to the notion of an intersection graph but differs from it in restricting the ways that the underlying objects are allowed to intersect each other.
Maria-Viktoria Hasse was a German mathematician who became the first female professor in the faculty of mathematics and science at TU Dresden. She wrote books on set theory and category theory, and is known as one of the namesakes of the Gallai–Hasse–Roy–Vitaver theorem in graph coloring.
Algorithms and Combinatorics is a book series in mathematics, and particularly in combinatorics and the design and analysis of algorithms. It is published by Springer Science+Business Media, and was founded in 1987.
