The sum of the two largest eigenvalues ★★

Author(s): Gernert

\begin{problem} Let $G$ be a graph on $n$ vertices and let $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n$ be the eigenvalues of $G$. Is $\lambda_1 + \lambda_2 \le n$? \end{problem}

Keywords: eigenvalues; spectrum

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

Fowler's Conjecture on eigenvalues of (3,6)-polyhedra ★★

Author(s): Fowler

\begin{conjecture} Let $G$ be the graph of a $(3,6)$-polyhedron with $2k + 4$ vertices. Then the eigenvalues of $G$ can be partitioned into three classes: $K = \{3, -1, -1, -1\}$, $P = {x_1, ..., x_k\}$ (where $x_i$ is nonnegative for $i = 1, \dots , k$), and $N = - P$. \end{conjecture}

Keywords: (3,6)-polyhedron; eigenvalues

Syndicate content