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.

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