Graph Theory » Basic G.T. » Connectivity

Kriesell's Conjecture ★★

Author(s): Kriesell

Conjecture   Let $ G $ be a graph and let $ T\subseteq V(G) $ such that for any pair $ u,v\in T $ there are $ 2k $ edge-disjoint paths from $ u $ to $ v $ in $ G $. Then $ G $ contains $ k $ edge-disjoint trees, each of which contains $ T $.

Keywords: Disjoint paths; edge-connectivity; spanning trees

Posted by Jon Noel
updated August 25th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

Conjecture   If $ G $ is a non-empty graph containing no induced odd cycle of length at least $ 5 $, then there is a $ 2 $-vertex colouring of $ G $ in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

Posted by Jon Noel
updated August 25th, 2013
add new comment

ZFC


ZF


Topology

Distributivity of a lattice of funcoids is not provable without axiom of choice ★

Author(s): Porton

Conjecture   Distributivity of the lattice $ \mathsf{FCD}(A;B) $ of funcoids (for arbitrary sets $ A $ and $ B $) is not provable in ZF (without axiom of choice).

A similar conjecture:

Conjecture   $ a\setminus^{\ast} b = a\#b $ for arbitrary filters $ a $ and $ b $ on a powerset cannot be proved in ZF (without axiom of choice).

Keywords: axiom of choice; distributive lattice; distributivity; funcoid; reverse math; reverse mathematics; ZF; ZFC

Posted by porton
updated August 24th, 2013
add new comment