Lovasz, Laszlo

Graph Theory » Coloring » Vertex coloring

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

Author(s): Erdos; Faber; Lovasz

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$ .

Keywords: chromatic number

Posted by Jon Noel
updated August 22nd, 2013

add new comment

Lovász Path Removal Conjecture ★★

Author(s): Lovasz

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.

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

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 chromatic number by two.

Conjecture $K_n$ is the only $n$ -chromatic double-critical graph

Keywords: coloring; complete graph

Posted by DFR
updated November 30th, 2009

Graph Theory » Basic G.T. » Matchings

Exponentially many perfect matchings in cubic graphs ★★★

Author(s): Lovasz; Plummer

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.

Keywords: cubic; perfect matching

Posted by mdevos
updated December 15th, 2010

Graph Theory » Algebraic G.T.

Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Problem Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

Posted by mdevos
updated March 18th, 2007

add new comment