Home » Author index

Lovasz, Laszlo


Graph Theory

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
2 comments
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
2 comments
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
Syndicate content