The graph-colorings tag has no wiki summary.

**3**

votes

**2**answers

505 views

### Where can I find a catalog of known Ramsey numbers?

Is there an online catalog available of Ramsey numbers, preferably one that for unknown values documents the known upper/lower bounds?

**4**

votes

**7**answers

2k views

### Suggest effective heuristic (not precise) graph colouring algorithm

Can you suggest a good rough graph colouring algorithm? What are the best such algorithms nowadays?

**9**

votes

**1**answer

604 views

### Which lattices have more than one minimal periodic coloring?

The lattice $\mathbb{Z}^n$ has an essentially unique (up to permutation) minimal periodic coloring for all $n$, namely the "checkerboard" 2-coloring. Here a coloring of a lattice $L$ is a coloring of ...

**17**

votes

**8**answers

4k views

### Why is edge-coloring less interesting than vertex-coloring?

I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate.
...

**3**

votes

**1**answer

1k views

### ? A graph is four colorable if and only if it is planar.

? A graph is four colorable if and only if it is planar.
Is this true, I know that if a graph is planar it is four colorable, but is it true that if a graph is four colorable it must be a planar ...

**5**

votes

**2**answers

340 views

### How are graph automorphisms are affected by transformations?

I have a heavily symmetric regular graph whose automorphisms I know. I remove one subgraph and insert another one in a consistent manner; for example, this could be a Delta-Y transformation ...

**11**

votes

**3**answers

729 views

### Is there a matrix whose permanent counts 3-colorings?

Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean:
Kirchhoff's theorem says that if you ...

**10**

votes

**9**answers

2k views

### What is the Tutte polynomial encoding?

Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...

**8**

votes

**5**answers

946 views

### Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number R(k). Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...