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

Keywords: coloring; hypercube

## Unfriendly partitions ★★★

Author(s): Cowan; Emerson

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 ★★

Author(s): Oporowski; Zhao

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.

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

Keywords: coloring; surface; 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 .

## 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