Deletion–contraction formula
id:
deletion-contraction-formula-173-9899333
title:
Deletion–contraction formula
text:
In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
- f ( G ) = f ( G ∖ e ) + f ( G / e ). Here G is a graph, f is a function on graphs, e is any edge of G, G \ e denotes edge deletion, and G / e denotes contraction. Tutte refers to such a function as a W-function. The formula is sometimes referred to as the fundamental reduction theorem. In this article we abbreviate to DC. R. M. Foster had already observed that the chromatic polynomial
brand slug:
wiki
category slug:
encyclopedia
description:
Formula in graph theory
original url:
https://en.wikipedia.org/wiki/Deletion%E2%80%93contraction_formula
date created:
2019-05-04T01:32:45Z
date modified:
2024-09-02T07:08:26Z
main entity:
{"identifier":"Q65067058","url":"https://www.wikidata.org/entity/Q65067058"}
image:
fields total:
13
integrity:
15