Home » Keyword index

edge-coloring


Combinatorics » Ramsey Theory

Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let $ Q_d $ denote the $ d $-dimensional cube graph. A map $ \phi : E(Q_d) \rightarrow \{0,1\} $ is called edge-antipodal if $ \phi(e) \neq \phi(e') $ whenever $ e,e' $ are antipodal edges.

Conjecture   If $ d \ge 2 $ and $ \phi : E(Q_d) \rightarrow \{0,1\} $ is edge-antipodal, then there exist a pair of antipodal vertices $ v,v' \in V(Q_d) $ which are joined by a monochromatic path.

Keywords: antipodal; cube; edge-coloring

Posted by mdevos
updated August 20th, 2010
5 comments
Graph Theory » Coloring » Edge coloring

Goldberg's conjecture ★★★

Author(s): Goldberg

The overfull parameter is defined as follows: \[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]

Conjecture   Every graph $ G $ satisfies $ \chi'(G) \le \max\{ \Delta(G) + 1, w(G) \} $.

Keywords: edge-coloring; multigraph

Posted by mdevos
updated June 5th, 2013
2 comments
Graph Theory » Coloring » Edge coloring

Seymour's r-graph conjecture ★★★

Author(s): Seymour

An $ r $-graph is an $ r $-regular graph $ G $ with the property that $ |\delta(X)| \ge r $ for every $ X \subseteq V(G) $ with odd size.

Conjecture   $ \chi'(G) \le r+1 $ for every $ r $-graph $ G $.

Keywords: edge-coloring; r-graph

Posted by mdevos
updated October 3rd, 2008
add new comment
Graph Theory » Directed Graphs » Tournaments

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 $ G $ be a tournament with edges colored from a set of three colors. Is it true that $ G $ must have either a rainbow directed cycle of length three or a vertex $ v $ so that every other vertex can be reached from $ v $ by a monochromatic (directed) path?

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 15th, 2008
add new comment
Graph Theory » Directed Graphs » Tournaments

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

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

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 9th, 2008
add new comment
Graph Theory » Coloring » Homomorphisms

Weak pentagon problem ★★

Author(s): Samal

Conjecture   If $ G $ is a cubic graph not containing a triangle, then it is possible to color the edges of $ G $ 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

Posted by Robert Samal
updated July 13th, 2007
add new comment
Graph Theory » Coloring » Edge coloring

List colorings of edge-critical graphs ★★

Author(s): Mohar

Conjecture   Suppose that $ G $ is a $ \Delta $-edge-critical graph. Suppose that for each edge $ e $ of $ G $, there is a list $ L(e) $ of $ \Delta $ colors. Then $ G $ is $ L $-edge-colorable unless all lists are equal to each other.

Keywords: edge-coloring; list coloring

Posted by Robert Samal
updated June 12th, 2007
add new comment
Graph Theory » Coloring » Edge coloring

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

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

Keywords: edge-coloring; hypergraph; Vizing

Posted by mdevos
updated June 23rd, 2009
1 comment
Graph Theory » Basic G.T. » Connectivity

Partitioning edge-connectivity ★★

Author(s): DeVos

Question   Let $ G $ be an $ (a+b+2) $-edge-connected graph. Does there exist a partition $ \{A,B\} $ of $ E(G) $ so that $ (V,A) $ is $ a $-edge-connected and $ (V,B) $ is $ b $-edge-connected?

Keywords: edge-coloring; edge-connectivity

Posted by mdevos
updated March 7th, 2007
add new comment
Graph Theory » Coloring » Edge coloring

Acyclic edge-colouring ★★

Author(s): Fiamcik

Conjecture   Every simple graph with maximum degree $ \Delta $ has a proper $ (\Delta+2) $-edge-colouring so that every cycle contains edges of at least three distinct colours.

Keywords: edge-coloring

Posted by mdevos
updated March 7th, 2007
add new comment
Syndicate content