# coloring

## Seagull problem ★★★

Author(s): Seymour

**Conjecture**Every vertex graph with no independent set of size has a complete graph on vertices as a minor.

Keywords: coloring; complete graph; minor

## Coloring squares of hypercubes ★★

Author(s): Wan

If is a simple graph, we let denote the simple graph with vertex set and two vertices adjacent if they are distance in .

**Conjecture**.

## Unfriendly partitions ★★★

If is a graph, we say that a partition of is *unfriendly* if every vertex has at least as many neighbors in the other classes as in its own.

**Problem**Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

## 5-coloring graphs with small crossing & clique numbers ★★

For a graph , we let denote the crossing number of , and we let denote the size of the largest complete subgraph of .

**Question**Does every graph with and have a 5-coloring?

Keywords: coloring; crossing number; planar graph

## Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The *Odd Distance Graph*, denoted , is the graph with vertex set and two points adjacent if the distance between them is an odd integer.

**Question**Is ?

Keywords: coloring; geometric graph; odd distance

## Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

**Conjecture**For every positive integer , every (loopless) graph with immerses .

Keywords: coloring; complete graph; immersion

## Bounding the chromatic number of graphs with no odd hole ★★★

Author(s): Gyarfas

**Conjecture**There exists a fixed function so that for every graph with no odd hole.

Keywords: chi-bounded; coloring; induced subgraph; odd hole; perfect graph

## 5-local-tensions ★★

Author(s): DeVos

**Conjecture**There exists a fixed constant (probably suffices) so that every embedded (loopless) graph with edge-width has a 5-local-tension.

## Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

**Conjecture**If is a simple graph which can be written as an union of edge-disjoint complete bipartite graphs, then .

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

## Bounded colorings for planar graphs ★★

Author(s): Alon; Ding; Oporowski; Vertigan

**Question**Does there exists a fixed function so that every planar graph of maximum degree has a partition of its vertex set into at most three sets so that for , every component of the graph induced by has size at most ?

Keywords: coloring; partition; planar graph