Given a graph G = (V,E), a vertex-deleted subgraph of G is a subgraph formed by deleting exactly one vertex from G. Clearly, it is an induced subgraph of G.For a graph G, the deck of G, denoted D(G), ...
An edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices it used to connect. An undirected graph H is a minor of another undirected graph G ...
The Petersen graph is the complement of the line graph of K_5. It is also the Kneser graph KG_{5,2}; this means that it has one vertex for each 2-element subset of a 5-element set, and two vertices ar ...
Let G = (V,E) be a directed graph and let M be an abelian group. A map φ: E → M is a flow or an M-flow if for every vertex v ∈ V, it holds that\sum_{e \in \delta^+(v)} \phi(e) = \sum_{e \in \delta^ ...
The most common percolation model is to take a regular lattice, like a square lattice, and make it into a random network by randomly "occupying" sites (vertices) or bonds (edges) with a statistically ...
The fact that the chromatic number of the plane must be at least four follows from the existence of a seven-vertex unit distance graph, named the Moser spindle after its discovery in 1961 by the broth ...
Selected results In his original paper, Rosa proved that an Eulerian graph with number of edges m ≡ 1 (mod 4) or m ≡ 2 (mod 4) can't be graceful.Also in his original paper, Rosa proved that the cycl ...
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 al ...
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that ...
Haddad Tardif (2004) introduced the problem with a story about seating assignment in committees: suppose that, in a university department, there are k committees, each consisting of k faculty members ...
An equivalent form of the Hadwiger conjecture (the contrapositive of the form stated above) is that, if there is no sequence of edge contractions (each merging the two endpoints of some edge into a si ...
In graph theory, a branch of mathematics, the Erd?s–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. More ...
In graph theory, the unproven Erd?s–Gyárfás conjecture, made in 1995 by the prolific mathematician Paul Erd?s and his collaborator András Gyárfás, states that every graph with minimum degree 3 ...
A planar graph is an undirected graph that can be embedded into the Euclidean plane without any crossings. A planar graph is called polyhedral if and only if it is 3-vertex-connected, that is, if ther ...
Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures.Graph In the most common sense of the term, a graph is an ordered ...
