edge-coloring


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 \emph{edge-antipodal} if $\phi(e) \neq \phi(e')$ whenever $e,e'$ are antipodal edges.

\begin{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. \end{conjecture}

Keywords: antipodal; cube; edge-coloring

Goldberg's conjecture ★★★

Author(s): Goldberg

The \emph{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. \]

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

Keywords: edge-coloring; multigraph

Seymour's r-graph conjecture ★★★

Author(s): Seymour

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

\begin{conjecture} $\chi'(G) \le r+1$ for every $r$-graph $G$. \end{conjecture}

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 \emph{rainbow} if all its edges have distinct colors, and \emph{monochromatic} if all its edges have the same color.

\begin{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? \end{problem}

Keywords: digraph; edge-coloring; tournament

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

\begin{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$? \end{problem}

Keywords: digraph; edge-coloring; tournament

Weak pentagon problem ★★

Author(s): Samal

\begin{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. \end{conjecture}

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

List colorings of edge-critical graphs ★★

Author(s): Mohar

\begin{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. \end{conjecture}

Keywords: edge-coloring; list coloring

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

\begin{conjecture} Let $H$ be a simple $d$-\Def[uniform]{hypergraph} 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. \end{conjecture}

Keywords: edge-coloring; hypergraph; Vizing

Partitioning edge-connectivity ★★

Author(s): DeVos

\begin{question} Let $G$ be an $(a+b+2)$-\Def[edge-connected]{connectivity (graph theory)} 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? \end{question}

Keywords: edge-coloring; edge-connectivity

Acyclic edge-colouring ★★

Author(s): Fiamcik

\begin{conjecture} Every simple graph with maximum degree $\Delta$ has a proper $(\Delta+2)$-\Def[edge-colouring]{edge-coloring} so that every cycle contains edges of at least three distinct colours. \end{conjecture}

Keywords: edge-coloring

Syndicate content