Circle graphIn graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other. gives an O(n2)-time algorithm that tests whether a given n-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it. A number of other problems that are NP-complete on general graphs have polynomial time algorithms when restricted to circle graphs.
Isthme (théorie des graphes)In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges. This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see bridge.
Ear decompositionIn graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear.
Polynôme chromatiqueEn mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe.
