# edge-coloring

## Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let denote the -dimensional cube graph. A map is called *edge-antipodal* if whenever are antipodal edges.

**Conjecture**If and is edge-antipodal, then there exist a pair of antipodal vertices which are joined by a monochromatic path.

Keywords: antipodal; cube; edge-coloring

## Goldberg's conjecture ★★★

Author(s): Goldberg

The *overfull parameter* is defined as follows:

**Conjecture**Every graph satisfies .

Keywords: edge-coloring; multigraph

## Seymour's r-graph conjecture ★★★

Author(s): Seymour

An -*graph* is an -regular graph with the property that for every with odd size.

**Conjecture**for every -graph .

Keywords: edge-coloring; r-graph

## Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is *rainbow* if all its edges have distinct colors, and *monochromatic* if all its edges have the same color.

**Problem**Let be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path?

Keywords: digraph; edge-coloring; tournament

## Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

**Problem**For every , is there a (least) positive integer so that whenever a tournament has its edges colored with colors, there exists a set of at most vertices so that every vertex has a monochromatic path to some point in ?

Keywords: digraph; edge-coloring; tournament

## Weak pentagon problem ★★

Author(s): Samal

**Conjecture**If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

## List colorings of edge-critical graphs ★★

Author(s): Mohar

**Conjecture**Suppose that is a -edge-critical graph. Suppose that for each edge of , there is a list of colors. Then is -edge-colorable unless all lists are equal to each other.

Keywords: edge-coloring; list coloring

## A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

**Conjecture**Let be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

## Partitioning edge-connectivity ★★

Author(s): DeVos

**Question**Let be an -edge-connected graph. Does there exist a partition of so that is -edge-connected and is -edge-connected?

Keywords: edge-coloring; edge-connectivity

## Acyclic edge-colouring ★★

Author(s): Fiamcik

**Conjecture**Every simple graph with maximum degree has a proper -edge-colouring so that every cycle contains edges of at least three distinct colours.

Keywords: edge-coloring