145,106
edits
Chromatic Polynomial: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
| Line 17: | Line 17: | ||
Computing the chromatic polynomial of a graph is a challenging problem. The most straightforward method is to use the deletion-contraction algorithm, which is based on the recursive formula: P(G, k) = P(G-e, k) - P(G/e, k), where G-e is the graph obtained by deleting an edge e from G, and G/e is the graph obtained by contracting e in G. However, this algorithm has exponential time complexity, making it impractical for large graphs. | Computing the chromatic polynomial of a graph is a challenging problem. The most straightforward method is to use the deletion-contraction algorithm, which is based on the recursive formula: P(G, k) = P(G-e, k) - P(G/e, k), where G-e is the graph obtained by deleting an edge e from G, and G/e is the graph obtained by contracting e in G. However, this algorithm has exponential time complexity, making it impractical for large graphs. | ||
[[Image:Detail-147043.jpg|thumb|center|A graph with vertices and edges, suitable for illustrating the concept of chromatic polynomial.]] | [[Image:Detail-147043.jpg|thumb|center|A graph with vertices and edges, suitable for illustrating the concept of chromatic polynomial.|class=only_on_mobile]] | ||
[[Image:Detail-147044.jpg|thumb|center|A graph with vertices and edges, suitable for illustrating the concept of chromatic polynomial.|class=only_on_desktop]] | |||
== Applications == | == Applications == | ||