Chromatic polynomial

# k-coloring
# k-coloring
entrance	Graph G with n vertices.
Output
Working hours	Belongs to P for . for . Otherwise for some constant
Complexity	#P -hard unless
Approximability	No FPRAS for

Chromatic polynomial
Chromatic polynomial
entrance	Graph G with n vertices.
Output	Coefficients
Working hours	for some constant
Complexity	#P is difficult
Reduced from	# 3SAT

All non-isomorphic graphs with 3 vertices and their chromatic polynomials are clockwise from above.
Independent 3-set:

k^{3}

{\ displaystyle k ^ {3}}

{\ displaystyle k ^ {3}}

.
Edge and one vertex:

k^{2}(k-1)

{\ displaystyle k ^ {2} (k-1)}

{\ displaystyle k ^ {2} (k-1)}

.
3 way:

k(k-1)^{2}

{\ displaystyle k (k-1) ^ {2}}

{\ displaystyle k (k-1) ^ {2}}

.
3 clicks:

k(k-1)(k-2)

{\ displaystyle k (k-1) (k-2)}

{\ displaystyle k (k-1) (k-2)}

.

Chromatic polynomial - a polynomial studied in algebraic graph theory . The polynomial considers the number of graph colorings as a function of the number of colors. The polynomial was originally identified by George David Birkhoff in an attempt to attack the four-color problem . The polynomial was generalized by H. Whitney and W. Tutt to the Tatt polynomial , associating it with statistical physics .

History

George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs in an attempt to prove the four-color theorem . If a $P(G,k)$ ${\ displaystyle P (G, k)}$ $P(G,k)$ denotes the number of correct colorings of the graph G with k colors, then one could prove the four color theorem by showing that $P(G,4)>0$ ${\ displaystyle P (G, 4)> 0}$ $P(G,4)>0$ for all planar graphs G. Thus, he hoped to use the power of mathematical analysis and algebra to study the roots of polynomials to study the combinatorial coloring problem.

Hassler Whitney summarized the Birkhoff polynomial from a planar case to general graphs in 1932. In 1968, Reed asked which polynomials are chromatic polynomials for some graphs (the question remains open) and introduced the concept of chromatically equivalent graphs. At present, chromatic polynomials are central objects of algebraic graph theory ^[1] .

Definition

All correct coloring graphs with 3 vertices when using k colors (

k=0,1,2,3

{\ displaystyle k = 0,1,2,3}

). The chromatic polynomial of each graph interpolates the number of correct colorings.

The chromatic polynomial of the graph G considers the number of regular colorings of the vertices . Usually a polynomial is denoted as $P_{G}(k)$ ${\ displaystyle P_ {G} (k)}$ $P_{G}(k)$ , $\chi _{G}(k)$ ${\ displaystyle \ chi _ {G} (k)}$ $\chi _{G}(k)$ , $\pi _{G}(k)$ ${\ displaystyle \ pi _ {G} (k)}$ $\pi _{G}(k)$ or $P(G,k)$ ${\ displaystyle P (G, k)}$ $P(G,k)$ . The last designation will be used in the rest of the article.

For example, the path $P_{3}$ ${\ displaystyle P_ {3}}$ $P_{3}$ with 3 vertices can not be painted in 0 colors or 1 color. Using 2 colors the graph can be colored in two ways. Using 3 color graphs can be colored in 12 ways.

Available colors $k$ ${\ displaystyle k}$	0	one	2	3
Number of colorings $P(P_{3},k)$ ${\ displaystyle P (P_ {3}, k)}$	0	0	2	12

For a graph G with n vertices, the chromatic polynomial is defined as a unique interpolating polynomial of degree not exceeding n , passing through the points

\left\{(0,P(G,0)),(1,P(G,1)),\cdots ,(n,P(G,n))\right\}.

{\ displaystyle \ left \ {(0, P (G, 0)), (1, P (G, 1)), \ cdots, (n, P (G, n)) \ right \}.}

If the graph G does not contain vertices with loops, then the chromatic polynomial is a reduced polynomial of degree exactly n . In fact, for the example above, we have

P(P_{3},t)=t(t-1)^{2},\qquad P(P_{3},3)=12.

{\ displaystyle P (P_ {3}, t) = t (t-1) ^ {2}, \ qquad P (P_ {3}, 3) = 12.}

The chromatic polynomial includes at least as much information about the colourability of G as it is contained in the chromatic number. Moreover, the chromatic number is the smallest positive integer at which the chromatic polynomial does not vanish,

\chi (G)=\min\{k:P(G,k)>0\}.

{\ displaystyle \ chi (G) = \ min \ {k: P (G, k)> 0 \}.}

Examples

Chromatic polynomials for some graphs
Triangle $K_{3}$ ${\ displaystyle K_ {3}}$	$t(t-1)(t-2)$ ${\ displaystyle t (t-1) (t-2)}$
Complete graph $K_{n}$ ${\ displaystyle K_ {n}}$	$t(t-1)(t-2)\cdots (t-(n-1))$ ${\ displaystyle t (t-1) (t-2) \ cdots (t- (n-1))}$
Way $P_{n}$ ${\ displaystyle P_ {n}}$	$t(t-1)^{n-1}$ ${\ displaystyle t (t-1) ^ {n-1}}$
Any tree with n vertices	$t(t-1)^{n-1}$ ${\ displaystyle t (t-1) ^ {n-1}}$
Cycle $C_{n}$ ${\ displaystyle C_ {n}}$	$(t-1)^{n}+(-1)^{n}(t-1)$ ${\ displaystyle (t-1) ^ {n} + (- 1) ^ {n} (t-1)}$
Count Petersen	$t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$ ${\ displaystyle t (t-1) (t-2) \ left (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ { 2} + 775t-352 \ right)}$

Properties

For a fixed graph G with n vertices, the chromatic polynomial $P(G,t)$ ${\ displaystyle P (G, t)}$ is, in fact, a polynomial of degree n . By definition, calculating the value of a polynomial $P(G,k)$ ${\ displaystyle P (G, k)}$ gives the k number of the graph G for $k=0,1,\cdots ,n$ ${\ displaystyle k = 0,1, \ cdots, n}$ . The same is true for k > n .

Expression

(-1)^{|V(G)|}P(G,-1)

{\ displaystyle (-1) ^ {| V (G) |} P (G, -1)}

gives the number of acyclic orientations of the graph G ^[2] .

The value of the derivative of the polynomial at point 1, $P'(G,1)$ ${\ displaystyle P '(G, 1)}$ equal to the sign of the chromatic invariant $\theta (G)$ ${\ displaystyle \ theta (G)}$ .

If the graph G has n vertices, m edges and c components $G_{1},\cdots ,G_{c}$ ${\ displaystyle G_ {1}, \ cdots, G_ {c}}$ then

Coefficients at $t^{0},\cdots ,t^{c-1}$ ${\ displaystyle t ^ {0}, \ cdots, t ^ {c-1}}$ are zero.
Coefficients at $t^{c},\cdots ,t^{n}$ ${\ displaystyle t ^ {c}, \ cdots, t ^ {n}}$ all non-zero.
Coefficient of $t^{n}$ ${\ displaystyle t ^ {n}}$ at $P(G,t)$ ${\ displaystyle P (G, t)}$ equals 1.
Coefficient of $t^{n-1}$ ${\ displaystyle t ^ {n-1}}$ at $P(G,t)$ ${\ displaystyle P (G, t)}$ equals $-m$ ${\ displaystyle -m}$ .
The coefficients of any chromatic polynomial are alternating.
The absolute values of the coefficients of any chromatic polynomial form a ^[3] .
$P(G,t)=P(G_{1},t)P(G_{2},t)\cdots P(G_{c},t)$ ${\ displaystyle P (G, t) = P (G_ {1}, t) P (G_ {2}, t) \ cdots P (G_ {c}, t)}$

A graph G with n vertices is a tree if and only if

P(G,t)=t(t-1)^{n-1}.

{\ displaystyle P (G, t) = t (t-1) ^ {n-1}.}

Chromatic equivalence

Three graphs with a chromatic polynomial equal to

(x-2)(x-1)^{3}x

{\ displaystyle (x-2) (x-1) ^ {3} x}

.

Two graphs are said to be chromatically equivalent if they have the same chromatic polynomials. Isomorphic graphs have the same chromatic polynomials, but non-isomorphic graphs can be chromatically equivalent. For example, all trees with n vertices have the same chromatic polynomials:

(x-1)^{n-1}x,

{\ displaystyle (x-1) ^ {n-1} x,}

In particular,

(x-1)^{3}x

{\ displaystyle (x-1) ^ {3} x}

is a chromatic polynomial for both a claw and a 4-vertex path .

Chromatic Uniqueness

A graph is chromatically unique if it is defined by a chromatic polynomial up to isomorphism. In other words, if the graph G is chromatically unique, then from $P(G,t)=P(H,t)$ ${\ displaystyle P (G, t) = P (H, t)}$ it follows that G and H are isomorphic.

All cycles are chromatically unique ^[4] .

Chromatic roots

The root (or zero ) of the chromatic polynomial (called the “chromatic root”) is the x value for which $P(G,x)=0$ ${\ displaystyle P (G, x) = 0}$ . Chromatic roots are well studied. In fact, Birkhoff’s initial impetus for introducing a chromatic polynomial was to show that for planar graphs $P(G,x)>0$ ${\ displaystyle P (G, x)> 0}$ for x ≥ 4. This would prove the four color theorem .

No graph can be colored in 0 colors, so 0 is always the chromatic root. Only graphs without edges can be colored in one color, so 1 is the chromatic root of any graph that has at least one edge. On the other hand, with the exception of these two cases, no graph can have a real number less than or equal to 32/27 as the chromatic root ^[5] . Result Tatta connects the golden section $\phi$ ${\ displaystyle \ phi}$ with the study of chromatic roots, showing that chromatic roots exist very close to $\phi ^{2}$ ${\ displaystyle \ phi ^ {2}}$ - if a $G_{n}$ ${\ displaystyle G_ {n}}$ is a planar triangulation of a sphere, then

P(G_{n},\phi ^{2})\leq \phi ^{5-n}.

{\ displaystyle P (G_ {n}, \ phi ^ {2}) \ leq \ phi ^ {5-n}.}

While the real line thus has large pieces that do not contain chromatic roots for any graph, any point on the complex plane is arbitrarily close to the chromatic root in the sense that there is an infinite family of graphs whose chromatic roots are dense on the complex plane ^[6] .

Categorization

The chromatic polynomial is categorized using homology theory, which is closely related to the ^[7] .

Algorithms

Computational problems associated with chromatic polynomials

finding chromatic polynomial $P(G,t)$ ${\ displaystyle P (G, t)}$ for a given graph G ;
calculation $P(G,k)$ ${\ displaystyle P (G, k)}$ at a fixed point k for a given graph G.

The first task is more general because, knowing the coefficients $P(G,t)$ ${\ displaystyle P (G, t)}$ , we can calculate the value of a polynomial at any point in polynomial time. The computational complexity of the second problem strongly depends on the value of k . When k is a natural number, the problem can be considered as a calculation of the number of k- colors of a given graph. For example, a task involves counting 3-colorings as a canonical problem for studying the complexity of counting. This task is complete in class #P .

Efficient Algorithms

For some base classes of graphs, explicit formulas for chromatic polynomials are known. For example, this is true for trees and clicks, as shown in the table above.

Polynomial time algorithms are known for calculating the chromatic polynomial for a wide class of graphs, which includes chordal graphs ^[8] and graphs with a limited clique width ^[9] ^[10] . The second of these classes, in turn, includes kografs and graphs with a limited tree width , such as external planar graphs .

There are people on the Internet who are trying to solve a problem collectively, and they are assisted by active autonomous helpers, especially for high-order chromatic polynomials ^[11] .

Dropping – stinging

The recursive method of calculating the chromatic polynomial is based on the edge tightening - for a pair of vertices $u$ ${\ displaystyle u}$ and $v$ ${\ displaystyle v}$ graph $G/uv$ ${\ displaystyle G / uv}$ is obtained by merging two vertices and removing an edge between them. The chromatic polynomial satisfies the recursive relation

P(G,k)=P(G-uv,k)-P(G/uv,k)

{\ displaystyle P (G, k) = P (G-uv, k) -P (G / uv, k)}

,

Where $u$ ${\ displaystyle u}$ and $v$ ${\ displaystyle v}$ are adjacent vertices and $G-uv$ ${\ displaystyle G-uv}$ is a graph with a remote edge $u v$ ${\ displaystyle uv}$ . Equivalent to

P(G,k)=P(G+uv,k)+P(G/uv,k)

{\ displaystyle P (G, k) = P (G + uv, k) + P (G / uv, k)}

if a $u$ ${\ displaystyle u}$ and $v$ ${\ displaystyle v}$ not adjacent and $G+uv$ ${\ displaystyle G + uv}$ is a graph with an added edge $u v$ ${\ displaystyle uv}$ . In the first form, the recursion stops on a set of empty graphs. These recurrence relations are also called the Fundamental reduction theorem ^[12] . Tatt ’s curiosity about which other properties of the graph satisfy the same recurrence relations led to the discovery of the generalization of the chromatic polynomial into two variables, the Tatt polynomial .

Expressions give a recursive procedure, called the removal – tightening algorithm , which is the basis of many graph coloring algorithms. The ChromaticPolynomial function in the computer algebra system Mathematica uses the second recurrent formula if the graph is dense, and the first if the graph is sparse ^[13] . The worst working time for both formulas satisfies the recurrence relation for Fibonacci numbers , so in the worst case the algorithm works for a time (up to a certain polynomial coefficient)

\phi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1{,}62^{n+m}\right)

{\ displaystyle \ phi ^ {n + m} = \ left ({\ frac {1 + {\ sqrt {5}}} {2}} \ right) ^ {n + m} \ in O \ left (1 { ,} 62 ^ {n + m} \ right)}

on a graph with n vertices and m edges ^[14] . Work time analysis can be improved to a polynomial number multiplier. $t(G)$ ${\ displaystyle t (G)}$ spanning trees of the input graph ^[15] . In practice, the branch and bound strategy is used together with dropping isomorphic graphs to eliminate recursive calls, and the time depends on the heuristics used when selecting a pair of vertices (for exclusion – contraction).

Cube Method

There is a natural geometric approach to coloring graphs, if we note that when assigning natural numbers to each vertex, the coloring of graphs is a vector of an integer lattice. Since assignment to two vertices $i$ ${\ displaystyle i}$ and $j$ ${\ displaystyle j}$ one color is equivalent to equality of coordinates $i$ ${\ displaystyle i}$ and $j$ ${\ displaystyle j}$ in the coloring vector, each edge can be associated with a hyperplane of the form $\{x\in R^{d}:x_{i}=x_{j}\}$ ${\ displaystyle \ {x \ in R ^ {d}: x_ {i} = x_ {j} \}}$ . A set of such hyperplanes for a given graph is called its graphical . The correct coloring of the graph is a coloring whose vector is not on a forbidden plane. Limited to many colors $k$ ${\ displaystyle k}$ the grid points fall into the cube $[0,k]^{n}$ ${\ displaystyle [0, k] ^ {n}}$ . In this context, the chromatic polynomial counts the lattice points in $[0,k]$ ${\ displaystyle [0, k]}$ -cube that do not fall on the graphical configuration.

Computational complexity

The task of calculating the number of 3-colorings of this graph is a canonical example of a #P- complete problem, so the problem of calculating the coefficients of a chromatic polynomial is # P-difficult. Similarly, the calculation $P(G,3)$ ${\ displaystyle P (G, 3)}$ for a given graph, G # is P-complete. On the other hand, for $k=0,1,2$ ${\ displaystyle k = 0,1,2}$ easy to calculate $P(G,k)$ ${\ displaystyle P (G, k)}$ , so that the corresponding tasks have a polynomial in time difficulty. For integers $k>3$ ${\ displaystyle k> 3}$ task # P-hard, which is set like a case $k=3$ ${\ displaystyle k = 3}$ . In fact, it is known that $P(G,x)$ ${\ displaystyle P (G, x)}$ # P-hard for all x (including negative integers and even all complex numbers), with the exception of three “simple points” ^[16] . Thus, the complexity of calculating the chromatic polynomial is completely clear.

In the polynomial

P(G,t)=a_{1}t+a_{2}t^{2}+\dots +a_{n}t^{n},

{\ displaystyle P (G, t) = a_ {1} t + a_ {2} t ^ {2} + \ dots + a_ {n} t ^ {n},}

coefficient $a_{n}$ ${\ displaystyle a_ {n}}$ always equal to 1, and some other coefficient properties are also known. This raises the question whether it is possible to calculate some simpler coefficients. However, the problem of calculating a _r for a fixed r and a given graph G is # P-difficult ^[17] .

No approximation algorithm is known. $P(G,x)$ ${\ displaystyle P (G, x)}$ for any x , except for three simple points. In integer points $k=3,4,\dots$ ${\ displaystyle k = 3,4, \ dots}$ the corresponding solvability problem of determining whether a given graph can be colored with k colors is NP-hard . Such problems cannot be approximated with any coefficient using a polynomial probabilistic algorithm with limited error, unless NP = RP, since any multiplicative approximation would distinguish between 0 and 1, which would be an effective solution to the problem using a polynomial probabilistic algorithm with a limited error in form solvability problem . In particular, under certain assumptions, this excludes the possibility of a fully polynomial randomized approximation scheme (FPRAS) . For other points, more complex reasoning is needed and the question is in the focus of active searches. As of 2008, it is known that there are no FPRAS schemes for calculating $P(G,x)$ ${\ displaystyle P (G, x)}$ for any x > 2, unless NP = RP ^[18] .

Notes

↑ Biggs, 1993 , p. Some chapters.
↑ Stanley, 1973 .
↑ Huh, 2012 .
↑ Chao, Whitehead, 1978 .
↑ Jackson, 1993 .
↑ Sokal, 2004 .
↑ Helme-Guizon, Rong, 2005 .
↑ Naor, Naor, Schaffer, 1987 .
↑ Giménez, Hliněný, Noy, 2005 .
↑ Makowsky, Rotics, Averbouch, Godlin, 2006 .
↑ Shirado, Christakis, 2017 , p. 370–374.
↑ Dong, Koh, Teo, 2005 .
↑ Pemmaraju, Skiena, 2003 .
↑ Wilf, 1986 .
↑ Sekine, Imai, Tani, 1995 .
↑ Yeager, Wertigan, and Welsh ( Jaeger, Vertigan, Welsh 1990 ), based on Linial's mixing ( Linial 1986 ).
↑ Oxley, Welsh, 2002 .
↑ Goldberg, Jerrum, 2008 .

Literature

Biggs N. Algebraic Graph Theory. - Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
Hirokazu Shirado, Nicholas A. Christakis. Locally noisy autonomous agents improve global human coordination in network experiments // Nature. - 2017. - V. 545 , no. 7654 . - p . 370–374 . - DOI : 10.1038 / nature22332 .
Chao C.-Y., Whitehead EG On chromatic equivalence of graphs // Theory and Applications of Graphs. — Springer, 1978. — Т. 642. — С. 121–131. — (Lecture Notes in Mathematics). — ISBN 978-3-540-08666-6 .
Dong FM, Koh KM, Teo KL Chromatic polynomials and chromaticity of graphs. — World Scientific Publishing Company, 2005. — ISBN 981-256-317-2 .
Giménez O., Hliněný P., Noy M. Computing the tatte polynomial on graphs of bounded clique-width // Proc. 31st int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005). - Springer-Verlag, 2005. - T. 3787. - P. 59–68. - DOI : 10.1007 / 11604686_6 .
Goldberg LA, Jerrum M. Inapproximability of the Tutte Polynomial // Information and Computation. - 2008. - T. 206 , no. 7 - p . 908 . - DOI : 10.1016 / j.ic.2008.04.003 .
Laure Helme-Guizon, Yongwu Rong. A categorification of the chromatic polynomial // Algebraic & Geometric Topology. - 2005. - V. 5 , no. 4 - p . 1365–1388 . - DOI : 10.2140 / agt.2005.5.1365 .
Huh J. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. - arXiv: 1008.4749v3, 2012.
Jackson B. A Zero-Free Interval for Chromatic Polynomials of Graphs // Combinatorics, Probability and Computing. - 1993. - T. 2 . - pp . 325–336 . - DOI : 10.1017 / S0963548300000705 .
Jaeger F., Vertigan DL, Welsh DJA On the computational complexity of the Jones and Tutte polynomials // Mathematical Proceedings of the Cambridge Philosophical Society. - 1990. - T. 108 . - pp . 35–53 . - DOI : 10.1017 / S0305004100068936 .
Linial N. Hard enumeration problems in geometry and combinatorics // SIAM J. Algebraic Discrete Methods. - 1986. - V. 7 , no. 2 - p . 331–335 . - DOI : 10.1137 / 0607036 .
Makowsky JA, Rotics U., Averbouch I., Godlin B. Computing graphs of bounded clique-width // Proc. 32nd int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006). - Springer-Verlag, 2006. - T. 4271. - p. 191–204. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 11917496_18 .
Naor J., Naor M., Schaffer A. Fast parallel algorithms // Proc. 19th ACM Symp. Theory of Computing (STOC '87). - 1987. - p. 355-364. - DOI : 10.1145 / 28395.28433 .
Oxley JG, Welsh DJA Chromatic, flow and reliability polynomials: The complexity of their coefficients. // Combinatorics, Probability and Computing . - 2002. - Vol. 11 , no. 4 - p . 403–426 .
Pemmaraju S., Skiena S. section 7.4.2 // Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. - Cambridge University Press, 2003. - ISBN 0-521-80686-0 .
Sekine K., Imai H., T. S. Springer, 1995. pp. 224–233.
Sokal AD Chromatic Roots are Dense in the Whole Complex Plane // Combinatorics, Probability and Computing . - 2004. - Vol. 13 , no. 2 - p . 221–261 . - DOI : 10.1017 / S0963548303006023 .
Stanley RP Acyclic orientations of graphs // Disc. Math . - 1973. - V. 5 , no. 2 - p . 171–178 . - DOI : 10.1016 / 0012-365X (73) 90108-8 .
Vitaly I. Voloshin. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications .. - American Mathematical Society, 2002. - ISBN 0-8218-2812-6 .
Wilf HS Algorithms and Complexity. - Prentice – Hall, 1986. - ISBN 0-13-021973-8 .

Links

Weisstein, Eric W. Chromatic polynomial (English) on the Wolfram MathWorld website.
Planetmat chromatic polynomial
Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [1]

[_f97ef9c5a321ea0e-1] Biggs, 1993 , p. Some chapters.

[_a1b00599676c2db5-2] Stanley, 1973 .

[_fc771153b3131b61-3] Huh, 2012 .

[_d035e951f418ebf2-4] Chao, Whitehead, 1978 .

[_d28468d6ef5f0fe8-5] Jackson, 1993 .

[_412197c24feb07db-6] Sokal, 2004 .

[_9af451017255f04e-7] Helme-Guizon, Rong, 2005 .

[_11e7d36ac322eb56-8] Naor, Naor, Schaffer, 1987 .

[_136484162b56b588-9] Giménez, Hliněný, Noy, 2005 .

[_dca30009eb2486c3-10] Makowsky, Rotics, Averbouch, Godlin, 2006 .

[_846d4bdc229dc385-11] Shirado, Christakis, 2017 , p. 370–374.

[_c22ae338821b10e6-12] Dong, Koh, Teo, 2005 .

[_01322ea229e12d63-13] Pemmaraju, Skiena, 2003 .

[_4e880c5fba0578e3-14] Wilf, 1986 .

[_cc401337562a184a-15] Sekine, Imai, Tani, 1995 .

[16] Yeager, Wertigan, and Welsh ( Jaeger, Vertigan, Welsh 1990 ), based on Linial's mixing ( Linial 1986 ).

[_a457b6f7b43c23b3-17] Oxley, Welsh, 2002 .

[_ebbc223e46f19004-18] Goldberg, Jerrum, 2008 .