# Lovasz, Laszlo

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

Author(s): Erdos; Faber; Lovasz

**Conjecture**If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .

Keywords: chromatic number

## Lovász Path Removal Conjecture ★★

Author(s): Lovasz

**Conjecture**There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.

Keywords:

## Double-critical graph conjecture ★★

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

**Conjecture**is the only -chromatic double-critical graph

Keywords: coloring; complete graph

## Exponentially many perfect matchings in cubic graphs ★★★

**Conjecture**There exists a fixed constant so that every -vertex cubic graph without a cut-edge has at least perfect matchings.

Keywords: cubic; perfect matching

## Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Keywords: cycle; hamiltonian; path; vertex-transitive