The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
2answers
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
7answers
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
1answer
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
8answers
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
1answer
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
2answers
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
3answers
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
9answers
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
5answers
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 ...