Graph Theory » Basic G.T. » Cycles

Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph $ G $, let $ cp(G) $ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $ cc(G) $ denote the cardinality of a minimum feedback vertex set (set of vertices $ X $ so that $ G-X $ is acyclic).

Conjecture   For every planar graph $ G $, $ cc(G)\leq 2cp(G) $.

Keywords: cycle packing; feedback vertex set; planar graph

Posted by cmlee
updated December 5th, 2019
3 comments
Combinatorics

Even vs. odd latin squares ★★★

Author(s): Alon; Tarsi

A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.

Conjecture   For every positive even integer $ n $, the number of even latin squares of order $ n $ and the number of odd latin squares of order $ n $ are different.

Keywords: latin square

Posted by mdevos
updated October 7th, 2007
add new comment