The graph-colorings tag has no wiki summary.

**7**

votes

**2**answers

408 views

### Simple proof that these graphs are perfect

I recently came across a family of infinite graphs (in the context of two-dimensional convexity) that don't have induced 4-paths (paths with 4 vertices).
Note that the complement of a 4-path is again ...

**25**

votes

**12**answers

4k views

### Strengthening the Induction Hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...

**47**

votes

**8**answers

6k views

### The “sensitivity” of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).
Let $C$ be a ...

**2**

votes

**2**answers

314 views

### Colourings of Graphs with extra conditions

As a phd-student I've wandered into a question of colourings of graphs and wondered what was known about them.
Given a finite graph G, where the maximum degree of a vertex is d, I'm interested in ...

**12**

votes

**6**answers

2k views

### A decision problem in graph coloring

It'll be great to get a pointer or answer to the following question:
What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily ...

**9**

votes

**1**answer

619 views

### Finding Two Rainbow Spanning Trees

Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.
Is the following problem ...

**10**

votes

**2**answers

533 views

### Can we select a rainbow matching if each degree is 6 and each colorclass is a C_6?

Suppose that we have a 2d-regular graph whose edges are colored such that the edges of each color form a cycle of length 2d. (So if the graph has 2n vertices, then there are n colors.) Is it true that ...

**1**

vote

**1**answer

91 views

### Graphical representation of duals of n-simplices

Is there any way to graphically represents the duals of n-simplices?
For example, I want to know how exactly duals of tetrahedrons arrange between themselves, i.e how many faces, volumes share the ...

**24**

votes

**3**answers

3k views

### Algebraic Proof of 4-Colour Theorem?

4-Colour Theorem. Every planar graph is 4-colourable.
This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism ...

**15**

votes

**1**answer

1k views

### Making a non-monotone function monotone

Consider a function $f: \{0,1\}^n \rightarrow \{1..R\}$. This function can be interpreted as a coloring $Color(v)$ of vertices in a unit n-dimensional hypercube in $R$ colors.
We say there is a ...

**5**

votes

**4**answers

1k views

### Coloring Points in the Plane

Suppose one wants to color the points in the plane so any two points at distance one apart are different colors. How many colors are needed?
I heard this problem when I was a kid. Back then the most ...

**3**

votes

**2**answers

518 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?

**10**

votes

**1**answer

611 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

733 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

952 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 ...