Faster access than browser!
61 relations: Algorithm, Annals of Mathematics, Apex graph, Béla Bollobás, Bipartite graph, Branch-decomposition, Cactus graph, Characterization (mathematics), Chordal graph, Claw-free graph, Cograph, Comparability graph, Complement graph, Complete bipartite graph, Complete graph, Cube, Cycle (graph theory), Diamond graph, Dual graph, Edge contraction, Erdős–Hajnal conjecture, Forbidden subgraph problem, Graph (discrete mathematics), Graph embedding, Graph minor, Graph operations, Graph theory, Graphs and Combinatorics, Hereditary property, Homeomorphism (graph theory), Hypergraph, If and only if, Induced subgraph, Kuratowski's theorem, Ladder graph, Line graph, Line graph of a hypergraph, Linkless embedding, List of age restrictions, Matroid minor, Octahedron, Outerplanar graph, Pentagonal prism, Perfect graph, Petersen family, Planar graph, Robertson–Seymour theorem, Series-parallel graph, Split graph, Star (graph theory), ..., Symposium on Foundations of Computer Science, Threshold graph, Time complexity, Tree (graph theory), Treewidth, Triangle-free graph, Trivially perfect graph, Wagner graph, Wagner's theorem, Zarankiewicz problem, 1-planar graph. Expand index (11 more) »
Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
New!!: Forbidden graph characterization and Algorithm · See more »
Annals of Mathematics
The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study.
New!!: Forbidden graph characterization and Annals of Mathematics · See more »
Apex graph
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex.
New!!: Forbidden graph characterization and Apex graph · See more »
Béla Bollobás
Béla Bollobás FRS (born 3 August 1943) is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory, and percolation.
New!!: Forbidden graph characterization and Béla Bollobás · See more »
Bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.
New!!: Forbidden graph characterization and Bipartite graph · See more »
Branch-decomposition
In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves.
New!!: Forbidden graph characterization and Branch-decomposition · See more »
Cactus graph
In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common.
New!!: Forbidden graph characterization and Cactus graph · See more »
Characterization (mathematics)
In mathematics, the statement that "Property P characterizes object X" means that not only does X have property P, but that X is the only thing that has property P. In other words, P is a defining property of X. It is also common to find statements such as "Property Q characterises Y up to isomorphism".
New!!: Forbidden graph characterization and Characterization (mathematics) · See more »
Chordal graph
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.
New!!: Forbidden graph characterization and Chordal graph · See more »
Claw-free graph
In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.
New!!: Forbidden graph characterization and Claw-free graph · See more »
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union.
New!!: Forbidden graph characterization and Cograph · See more »
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order.
New!!: Forbidden graph characterization and Comparability graph · See more »
Complement graph
In graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in.
New!!: Forbidden graph characterization and Complement graph · See more »
Complete bipartite graph
No description.
New!!: Forbidden graph characterization and Complete bipartite graph · See more »
Complete graph
No description.
New!!: Forbidden graph characterization and Complete graph · See more »
Cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex.
New!!: Forbidden graph characterization and Cube · See more »
Cycle (graph theory)
In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.
New!!: Forbidden graph characterization and Cycle (graph theory) · See more »
Diamond graph
In the mathematical field of graph theory, the diamond graph is a planar undirected graph with 4 vertices and 5 edges.
New!!: Forbidden graph characterization and Diamond graph · See more »
Dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of.
New!!: Forbidden graph characterization and Dual graph · See more »
Edge contraction
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined.
New!!: Forbidden graph characterization and Edge contraction · See more »
Erdős–Hajnal conjecture
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.
New!!: Forbidden graph characterization and Erdős–Hajnal conjecture · See more »
Forbidden subgraph problem
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges in an n-vertex graph which does not have a subgraph isomorphic to G. In this context, G is called a forbidden subgraph.
New!!: Forbidden graph characterization and Forbidden subgraph problem · See more »
Graph (discrete mathematics)
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".
New!!: Forbidden graph characterization and Graph (discrete mathematics) · See more »
Graph embedding
In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of) are associated with edges in such a way that.
New!!: Forbidden graph characterization and Graph embedding · See more »
Graph minor
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 and vertices and by contracting edges.
New!!: Forbidden graph characterization and Graph minor · See more »
Graph operations
Graph operations produce new graphs from initial ones.
New!!: Forbidden graph characterization and Graph operations · See more »
Graph theory
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
New!!: Forbidden graph characterization and Graph theory · See more »
Graphs and Combinatorics
Graphs and Combinatorics (ISSN 0911-0119, abbreviated Graphs Combin.) is a peer-reviewed academic journal in graph theory and combinatorics published by Springer Japan.
New!!: Forbidden graph characterization and Graphs and Combinatorics · See more »
Hereditary property
In mathematics, a hereditary property is a property of an object, that inherits to all its subobjects, where the term subobject depends on the context.
New!!: Forbidden graph characterization and Hereditary property · See more »
Homeomorphism (graph theory)
In graph theory, two graphs G and G' are homeomorphic if there is a graph isomorphism from some subdivision of G to some subdivision of G'.
New!!: Forbidden graph characterization and Homeomorphism (graph theory) · See more »
Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices.
New!!: Forbidden graph characterization and Hypergraph · See more »
If and only if
In logic and related fields such as mathematics and philosophy, if and only if (shortened iff) is a biconditional logical connective between statements.
New!!: Forbidden graph characterization and If and only if · See more »
Induced subgraph
In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.
New!!: Forbidden graph characterization and Induced subgraph · See more »
Kuratowski's theorem
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski.
New!!: Forbidden graph characterization and Kuratowski's theorem · See more »
Ladder graph
In the mathematical field of graph theory, the ladder graph Ln is a planar undirected graph with 2n vertices and 3n-2 edges.
New!!: Forbidden graph characterization and Ladder graph · See more »
Line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both and used the construction before this.
New!!: Forbidden graph characterization and Line graph · See more »
Line graph of a hypergraph
The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two hyperedges adjacent when they have a nonempty intersection.
New!!: Forbidden graph characterization and Line graph of a hypergraph · See more »
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph are linked.
New!!: Forbidden graph characterization and Linkless embedding · See more »
List of age restrictions
This article gives an outline of age restrictions.19.
New!!: Forbidden graph characterization and List of age restrictions · See more »
Matroid minor
In the mathematical theory of matroids, a minor of a matroid M is another matroid N that is obtained from M by a sequence of restriction and contraction operations.
New!!: Forbidden graph characterization and Matroid minor · See more »
Octahedron
In geometry, an octahedron (plural: octahedra) is a polyhedron with eight faces, twelve edges, and six vertices.
New!!: Forbidden graph characterization and Octahedron · See more »
Outerplanar graph
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
New!!: Forbidden graph characterization and Outerplanar graph · See more »
Pentagonal prism
In geometry, the pentagonal prism is a prism with a pentagonal base.
New!!: Forbidden graph characterization and Pentagonal prism · See more »
Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph.
New!!: Forbidden graph characterization and Perfect graph · See more »
Petersen family
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6.
New!!: Forbidden graph characterization and Petersen family · See more »
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
New!!: Forbidden graph characterization and Planar graph · See more »
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.
New!!: Forbidden graph characterization and Robertson–Seymour theorem · See more »
Series-parallel graph
In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations.
New!!: Forbidden graph characterization and Series-parallel graph · See more »
Split graph
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set.
New!!: Forbidden graph characterization and Split graph · See more »
Star (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves (but, no internal nodes and k + 1 leaves when k ≤ 1).
New!!: Forbidden graph characterization and Star (graph theory) · See more »
Symposium on Foundations of Computer Science
The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science.
New!!: Forbidden graph characterization and Symposium on Foundations of Computer Science · See more »
Threshold graph
In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations.
New!!: Forbidden graph characterization and Threshold graph · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: Forbidden graph characterization and Time complexity · See more »
Tree (graph theory)
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.
New!!: Forbidden graph characterization and Tree (graph theory) · See more »
Treewidth
In graph theory, the treewidth of an undirected graph is a number associated with the graph.
New!!: Forbidden graph characterization and Treewidth · See more »
Triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges.
New!!: Forbidden graph characterization and Triangle-free graph · See more »
Trivially perfect graph
In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques.
New!!: Forbidden graph characterization and Trivially perfect graph · See more »
Wagner graph
In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges.
New!!: Forbidden graph characterization and Wagner graph · See more »
Wagner's theorem
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices).
New!!: Forbidden graph characterization and Wagner's theorem · See more »
Zarankiewicz problem
The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices but has no complete bipartite subgraphs of a given size.
New!!: Forbidden graph characterization and Zarankiewicz problem · See more »
1-planar graph
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge.
New!!: Forbidden graph characterization and 1-planar graph · See more »
Redirects here:
Forbidden graph, Forbidden induced subgraph, Forbidden minor, Forbidden minor characterization, Forbidden minors.
References
[1] https://en.wikipedia.org/wiki/Forbidden_graph_characterization
