# List of combinatorial problems

I have a list of problems that I am currently thinking about. It’s quite difficult to judge which one is easy or whether a conjecture is true. But all of them seems to be important enough, in the sense of the possibility to initiate a whole new branch of combinatorics. I also mark their importance (in my opinion) by stars. Certainly there are many other important open problems, here is just a very small collection of them, those I spent at least a couple of hours on.

**A. Graph coloring:**

1. Erdos-Faber-Lovasz conjecture ✭✭✭✭

2. Hedetniemi conjecture ✭✭✭✭

3. Chromatic number of Cayley graph ✭✭✭✭

4. Doubly critical graph conjecture ✭✭

Common points: Chromatic number is NP-hard, but for graphs with nice algebraic structures, maybe we can characterize it. It’s also possible to find some other also-NP-hard equivalent description of chromatic number, which is easier to study for specific problems.

**B. Traditional Graph Theory:**

1. Seymour’s second neighborhood conjecture ✭✭✭✭

**C. Correlation Inequality:**

1. Bunkbed conjecture ✭✭✭✭

**D. Extremal Combinatorics:**

1. Generalization of Sperner Lemma ✭✭✭

**E. Combinatorial Geometry:**

1. Unit distance problem ✭✭✭✭

2. Kusner conjecture (l1 distance) ✭✭✭✭

### Leave a Comment

Be the first to comment!

## Leave a Reply