# Tagged Questions

Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.

377 views

### coloring in lattice

This is a mathematical question raised from engineering and physics: Is there some established mathematical approach in filling a physical lattice with some colored basis (black and white here)? For ...
5k views

### Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors. The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...
5k 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 ...
998 views

### A Question on 1, 2 ,3 Conjecture

The 1, 2, 3 conjecture is well-known: If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the ...
274 views

### Coloring a Ferrers diagram

I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed. Say that a coloring of the dots of a Ferrers ...
3k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
1k 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 ...
651 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 ...
393 views

### Postnikov's approach to perfect matchings of graphs

Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new ...
389 views

### Has there been a computer search for a 5-chromatic unit distance graph?

The existence of a 4-chromatic unit distance graph (e.g., the Moser spindle) establishes a lower bound of 4 for the chromatic number of the plane (see the Nelson-Hadwiger problem). Obviously, it ...
Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices. Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$. The edge set ...