Loading...
Please wait, while we are loading the content...
Similar Documents
On approximately counting colourings of small degree graphs (1999)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bubley, Russ Dyer, Martin Greenhill, Catherine Jerrum, Mark |
| Abstract | We consider approximate counting of colourings of an n-vertex graph using rapidly mixing Markov chains. It has been shown by Jerrum and by Salas and Sokal that a simple random walk on graph colourings would mix rapidly provided the number of colours, k, exceeded the maximum degree ∆ of the graph by a factor of at least 2. Lack of improvements on this bound led to the conjecture that k ≥ 2∆ was a natural barrier. We disprove this conjecture in the simplest case of 5-colouring graphs of maximum degree 3. Our proof involves a computer-assisted proof tech-nique to establish rapid mixing of a new “heat bath ” Markov chain on colourings using the method of path coupling. We outline an extension to 7-colourings of triangle-free 4-regular graphs. Since rapid mixing implies approximate counting in polynomial time, we show in contrast that exact counting is unlikely to be pos-sible (in polynomial time). We give a general proof that the problem of exactly counting the number of proper k-colourings of graphs with maximum degree ∆ is #P-complete whenever k ≥ 3 and ∆ ≥ 3. 1 |
| File Format | |
| Journal | SIAM Journal on Computing |
| Language | English |
| Publisher Date | 1999-01-01 |
| Access Restriction | Open |
| Subject Keyword | Small Degree Graph Polynomial Time Maximum Degree N-vertex Graph Rapid Mixing Graph Colouring Approximate Counting Exact Counting General Proof Simple Random Walk Natural Barrier Path Coupling Proper K-colourings Computer-assisted Proof Tech-nique Markov Chain New Heat Bath Markov Chain Triangle-free 4-regular Graph 5-colouring Graph |
| Content Type | Text |
| Resource Type | Article |
