Faster access than browser!
59 relations: Binary relation, Chordal completion, Clique (graph theory), Clique problem, Clique-width, Cluster graph, Comparability graph, Complement graph, Complemented lattice, Complete bipartite graph, Complete graph, Connected component (graph theory), Courcelle's theorem, Discrete Applied Mathematics, Disjoint union, Disjoint union of graphs, Distance (graph theory), Distance-hereditary graph, Forbidden graph characterization, Glossary of graph theory terms, Graph (discrete mathematics), Graph coloring, Graph isomorphism, Graph theory, Greedy coloring, Grundy number, Hamiltonian path problem, Hereditary property, Induced path, Induced subgraph, Information Processing Letters, Journal of Combinatorial Theory, Journal of Graph Theory, Kruskal's tree theorem, Lexicographic breadth-first search, Logic of graphs, Lowest common ancestor, Maximal independent set, Modular decomposition, NP-completeness, Parameterized complexity, Partially ordered set, Partition refinement, Path (graph theory), Perfect graph, Perfectly orderable graph, Permutation graph, Planar graph, Read-once function, Separable permutation, ..., Series-parallel partial order, Shortest path problem, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Split (graph theory), Threshold graph, Trivially perfect graph, Turán graph, Well-quasi-ordering. Expand index (9 more) »
Binary relation
In mathematics, a binary relation on a set A is a set of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2.
New!!: Cograph and Binary relation · See more »
Chordal completion
In graph theory, a branch of mathematics, a chordal completion of a given undirected graph is a chordal graph, on the same vertex set, that has as a subgraph.
New!!: Cograph and Chordal completion · See more »
Clique (graph theory)
In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.
New!!: Cograph and Clique (graph theory) · See more »
Clique problem
In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph.
New!!: Cograph and Clique problem · See more »
Clique-width
In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs.
New!!: Cograph and Clique-width · See more »
Cluster graph
In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs.
New!!: Cograph and Cluster graph · 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!!: Cograph 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!!: Cograph and Complement graph · See more »
Complemented lattice
In the mathematical discipline of order theory, a complemented lattice is a bounded lattice (with least element 0 and greatest element 1), in which every element a has a complement, i.e. an element b satisfying a ∨ b.
New!!: Cograph and Complemented lattice · See more »
Complete bipartite graph
No description.
New!!: Cograph and Complete bipartite graph · See more »
Complete graph
No description.
New!!: Cograph and Complete graph · See more »
Connected component (graph theory)
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
New!!: Cograph and Connected component (graph theory) · See more »
Courcelle's theorem
In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth.
New!!: Cograph and Courcelle's theorem · See more »
Discrete Applied Mathematics
Discrete Applied Mathematics is a peer-reviewed academic journal in mathematics, published by Elsevier.
New!!: Cograph and Discrete Applied Mathematics · See more »
Disjoint union
In set theory, the disjoint union (or discriminated union) of a family of sets is a modified union operation that indexes the elements according to which set they originated in.
New!!: Cograph and Disjoint union · See more »
Disjoint union of graphs
In graph theory, a branch of mathematics, the disjoint union of graphs is an operation that combines two or more graphs to form a larger graph.
New!!: Cograph and Disjoint union of graphs · See more »
Distance (graph theory)
In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them.
New!!: Cograph and Distance (graph theory) · See more »
Distance-hereditary graph
In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph.
New!!: Cograph and Distance-hereditary graph · See more »
Forbidden graph characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.
New!!: Cograph and Forbidden graph characterization · See more »
Glossary of graph theory terms
This is a glossary of graph theory terms.
New!!: Cograph and Glossary of graph theory terms · 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!!: Cograph and Graph (discrete mathematics) · See more »
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.
New!!: Cograph and Graph coloring · See more »
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.
New!!: Cograph and Graph isomorphism · 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!!: Cograph and Graph theory · See more »
Greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color.
New!!: Cograph and Greedy coloring · See more »
Grundy number
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.
New!!: Cograph and Grundy number · See more »
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).
New!!: Cograph and Hamiltonian path problem · 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!!: Cograph and Hereditary property · See more »
Induced path
In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.
New!!: Cograph and Induced path · 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!!: Cograph and Induced subgraph · See more »
Information Processing Letters
Information Processing Letters is a peer reviewed scientific journal in the field of computer science, published by Elsevier.
New!!: Cograph and Information Processing Letters · See more »
Journal of Combinatorial Theory
The Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas.
New!!: Cograph and Journal of Combinatorial Theory · See more »
Journal of Graph Theory
The Journal of Graph Theory is a peer-reviewed mathematics journal specializing in graph theory and related areas, such as structural results about graphs, graph algorithms with theoretical emphasis, and discrete optimization on graphs.
New!!: Cograph and Journal of Graph Theory · See more »
Kruskal's tree theorem
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.
New!!: Cograph and Kruskal's tree theorem · See more »
Lexicographic breadth-first search
In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph.
New!!: Cograph and Lexicographic breadth-first search · See more »
Logic of graphs
In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using logical formulas.
New!!: Cograph and Logic of graphs · See more »
Lowest common ancestor
In graph theory and computer science, the lowest common ancestor (LCA) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where we define each node to be a descendant of itself (so if has a direct connection from, is the lowest common ancestor).
New!!: Cograph and Lowest common ancestor · See more »
Maximal independent set
In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set.
New!!: Cograph and Maximal independent set · See more »
Modular decomposition
In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph.
New!!: Cograph and Modular decomposition · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: Cograph and NP-completeness · See more »
Parameterized complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output.
New!!: Cograph and Parameterized complexity · See more »
Partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set.
New!!: Cograph and Partially ordered set · See more »
Partition refinement
In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets.
New!!: Cograph and Partition refinement · See more »
Path (graph theory)
In graph theory, a path in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another.
New!!: Cograph and Path (graph theory) · 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!!: Cograph and Perfect graph · See more »
Perfectly orderable graph
In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph.
New!!: Cograph and Perfectly orderable graph · See more »
Permutation graph
In mathematics, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation.
New!!: Cograph and Permutation graph · 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!!: Cograph and Planar graph · See more »
Read-once function
In mathematics, a read-once function is a special type of Boolean function that can be described by a Boolean expression in which each variable appears only once.
New!!: Cograph and Read-once function · See more »
Separable permutation
In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums.
New!!: Cograph and Separable permutation · See more »
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations.
New!!: Cograph and Series-parallel partial order · See more »
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
New!!: Cograph and Shortest path problem · See more »
SIAM Journal on Computing
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science.
New!!: Cograph and SIAM Journal on Computing · See more »
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM).
New!!: Cograph and SIAM Journal on Discrete Mathematics · See more »
Split (graph theory)
In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph.
New!!: Cograph and Split (graph theory) · 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!!: Cograph and Threshold 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!!: Cograph and Trivially perfect graph · See more »
Turán graph
No description.
New!!: Cograph and Turán graph · See more »
Well-quasi-ordering
In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x_0, x_1, x_2, … from X contains an increasing pair x_i\le x_j with i.
New!!: Cograph and Well-quasi-ordering · See more »
Redirects here:
Co-graph, Complement reducible graph, Complement-reducible graph, Cotree, P 4 free graph, P 4-free graph, P4 free graph, P4-free graph.
References
[1] https://en.wikipedia.org/wiki/Cograph
