Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!
New! » Create account

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. [1]

35 relations: Binary relation, Clique (graph theory), Clique problem, Clique-width, Comparability graph, Complement graph, Complemented lattice, Complete bipartite graph, Complete graph, Connected component (graph theory), Distance (graph theory), Distance-hereditary graph, Forbidden graph characterization, Glossary of graph theory, Graph (mathematics), Graph coloring, Graph isomorphism, Graph operations, Graph theory, Hamiltonian path problem, Information Processing Letters, Kruskal's tree theorem, Lowest common ancestor, Maximal independent set, Modular decomposition, Partition refinement, Path (graph theory), Perfect graph, Permutation graph, Planar graph, Separable permutation, Series-parallel partial order, Threshold graph, Turán graph, Well-quasi-ordering.

Binary relation

In mathematics, a binary relation on a set A is a collection 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 »

Clique (graph theory)

In the mathematical area of graph theory, a clique is subset of vertices of an undirected graph, such that its induced subgraph is complete; that is, every two distinct vertices in the clique are adjacent.

New!!: Cograph and Clique (graph theory) · See more »

Clique problem

In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.

New!!: Cograph and Clique problem · See more »


In graph theory, the clique-width of a graph G is the minimum number of labels needed to construct G by means of the following 4 operations.

New!!: Cograph and Clique-width · 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 G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.

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 »

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

Graph theory is a growing area in mathematical research, and has a large specialized vocabulary.

New!!: Cograph and Glossary of graph theory · See more »

Graph (mathematics)

In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links.

New!!: Cograph and Graph (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 generally called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.

New!!: Cograph and Graph isomorphism · See more »

Graph operations

Graph operations produce new graphs from initial ones.

New!!: Cograph and Graph operations · See more »

Graph theory

In mathematics and computer science, 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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

Turán graph

No description.

New!!: Cograph and Turán graph · See more »


In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering that is well-founded, meaning 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:

Complement reducible graph, Complement-reducible graph, Cotree, P 4 free graph, P 4-free graph, P4 free graph, P4-free graph.


[1] https://en.wikipedia.org/wiki/Cograph

Hey! We are on Facebook now! »