Lovasz, Laszlo


Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

\begin{conjecture} If $G$ is a simple graph which is the union of $k$ pairwise edge-disjoint complete graphs, each of which has $k$ vertices, then the chromatic number of $G$ is $k$. \end{conjecture}

Keywords: chromatic number

Lovász Path Removal Conjecture ★★

Author(s): Lovasz

\begin{conjecture} There is an integer-valued function $f(k)$ such that if $G$ is any $f(k)$-connected graph and $x$ and $y$ are any two vertices of $G$, then there exists an induced path $P$ with ends $x$ and $y$ such that $G-V(P)$ is $k$-connected. \end{conjecture}

Keywords:

Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph $G$ is called double-critical, if removing any pair of adjacent vertexes lowers the \Def{chromatic number} by two.

\begin{conjecture} $K_n$ is the only $n$-chromatic double-critical graph \end{conjecture}

Keywords: coloring; complete graph

Exponentially many perfect matchings in cubic graphs ★★★

Author(s): Lovasz; Plummer

\begin{conjecture} There exists a fixed constant $c$ so that every $n$-vertex cubic graph without a cut-edge has at least $e^{cn}$ perfect matchings. \end{conjecture}

Keywords: cubic; perfect matching

Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

\begin{problem} Does every connected \Def{vertex-transitive graph} have a \Def{Hamiltonian path}? \end{problem}

Keywords: cycle; hamiltonian; path; vertex-transitive

Syndicate content