Graph Theory » Topological G.T. » Drawings

Straight line representation of planar linear hypergraphs ★★

Author(s): de Fraysseix; Ossona de Mendez

Conjecture   Every planar linear hypergraph $ \mathcal H $ has a straight line representation in the plane which maps each vertex $ v $ to a point $ p(v) $ and each edge $ E $ to a straight line segment $ s(E) $, in such a way that:
    \item for each vertex $ v $ and each edge $ E $, we have: $$p(v)\in s(E)\quad\iff\quad v\in E$$ \item for each couple of distinct edges $ E_1,E_2 $, we have $$s(E_1)\cap s(E_2)=\{p(v): v\in E_1\cap E_2\}$$

Keywords: intersection graph; planar hypergraph

Posted by taxipom
updated September 4th, 2007
add new comment
Graph Theory » Coloring » Vertex coloring

Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

Conjecture   For every positive integer $ t $, every (loopless) graph $ G $ with $ \chi(G) \ge t $ immerses $ K_t $.

Keywords: coloring; complete graph; immersion

Posted by mdevos
updated September 4th, 2007
add new comment