Edge coloring


Petersen coloring conjecture ★★★

Author(s): Jaeger

\begin{conjecture} Let $G$ be a \Def[cubic]{cubic graph} graph with no \Def[bridge]{bridge (graph theory)}. Then there is a coloring of the edges of $G$ using the edges of the \Def[Petersen]{petersen graph} graph so that any three mutually adjacent edges of $G$ map to three mutually adjancent edges in the Petersen graph. \end{conjecture}

Keywords: cubic; edge-coloring; Petersen graph

Packing T-joins ★★

Author(s): DeVos

\begin{conjecture} There exists a fixed constant $c$ (probably $c=1$ suffices) so that every graft with minimum $T$-cut size at least $k$ contains a $T$-join packing of size at least $(2/3)k-c$. \end{conjecture}

Keywords: packing; T-join

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

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

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

Universal Steiner triple systems ★★

Author(s): Grannell; Griggs; Knor; Skoviera

\begin{problem} Which \href [Steiner triple systems]{http://mathworld.wolfram.com/SteinerTripleSystem.html} are universal? \end{problem}

Keywords: cubic graph; Steiner triple system

Edge list coloring conjecture ★★★

Author(s):

\begin{conjecture} Let $G$ be a loopless multigraph. Then the edge chromatic number of $G$ equals the list edge chromatic number of $G$. \end{conjecture}

Keywords:

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

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

Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph $G$ is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index $s\chi'(G)$ is the minimum number of colours in a strong edge-colouring of $G$.

\begin{conjecture} $$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$ $$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$ \end{conjecture}

Keywords:


Syndicate content