Alon, Noga


Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

\begin{conjecture} If $G$ is a $k$-regular directed graph with no parallel arcs, then $G$ contains a collection of ${k+1 \choose 2}$ arc-disjoint directed cycles. \end{conjecture}

Keywords:

PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

\begin{question} Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments? \end{question}

Keywords: feedback arc set; PTAS; tournament

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

\begin{conjecture} There is a constant $c$ such that the list chromatic number of any bipartite graph $G$ of maximum degree $\Delta$ is at most $c \log \Delta$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

\begin{problem} Is there a minimum integer $f(d)$ such that the vertices of any digraph with minimum outdegree $d$ can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least $d$? \end{problem}

Keywords:

Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

\begin{conjecture} For every $\epsilon > 0$ and every positive integer $k$, there exists $r_0 = r_0(\epsilon,k)$ so that every simple $r$-regular graph $G$ with $r \ge r_0$ has a $k$-regular subgraph $H$ with $|V(H)| \ge (1- \epsilon) |V(G)|$. \end{conjecture}

Keywords: regular; subgraph

Even vs. odd latin squares ★★★

Author(s): Alon; Tarsi

A \Def{latin square} is \emph{even} if the product of the signs of all of the row and column permutations is 1 and is \emph{odd} otherwise.

\begin{conjecture} For every positive even integer $n$, the number of even latin squares of order $n$ and the number of odd latin squares of order $n$ are different. \end{conjecture}

Keywords: latin square

Ramsey properties of Cayley graphs ★★★

Author(s): Alon

\begin{conjecture} There exists a fixed constant $c$ so that every abelian group $G$ has a subset $S \subseteq G$ with $-S = S$ so that the \Def[Cayley graph]{cayley graph} ${\mathit Cayley}(G,S)$ has no clique or independent set of size $> c \log |G|$. \end{conjecture}

Keywords: Cayley graph; Ramsey number

Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

\begin{conjecture} If $G$ is a simple graph which can be written as an union of $m$ edge-disjoint complete bipartite graphs, then $\chi(G) \le m+1$. \end{conjecture}

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Bounded colorings for planar graphs ★★

Author(s): Alon; Ding; Oporowski; Vertigan

\begin{question} Does there exists a fixed function $f : {\mathbb N} \rightarrow {\mathbb N}$ so that every \Def[planar]{planar graph} graph of maximum degree $d$ has a partition of its vertex set into at most three sets $\{V_1,V_2,V_3\}$ so that for $i=1,2,3$, every component of the graph induced by $V_i$ has size at most $f(d)$? \end{question}

Keywords: coloring; partition; planar graph

Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let $r$ be a positive integer. We say that a graph $G$ is strongly $r$-colorable if for every partition of the vertices to sets of size at most $r$ there is a proper $r$-coloring of $G$ in which the vertices in each set of the partition have distinct colors.

\begin{conjecture} If $\Delta$ is the maximal degree of a graph $G$, then $G$ is strongly $2 \Delta$-colorable. \end{conjecture}

Keywords: strong coloring

Syndicate content