Recent Activity

Problem What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?

Keywords:

Posted by fhavet
updated March 6th, 2013

add new comment

Graph Theory » Extremal G.T.

Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

Conjecture If $G$ has at most $k$ edge-disjoint triangles, then there is a set of $2k$ edges whose deletion destroys every triangle.

Keywords:

Posted by fhavet
updated March 6th, 2013

add new comment

Graph Theory » Extremal G.T.

Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

Conjecture If $G$ is a simple triangle-free graph, then there is a set of at most $n^2/25$ edges whose deletion destroys every odd cycle.

Keywords:

Posted by fhavet
updated March 6th, 2013

add new comment

Graph Theory » Hypergraphs

Simultaneous partition of hypergraphs ★★

Author(s): Kühn; Osthus

Problem Let $H_1$ and $H_2$ be two $r$ -uniform hypergraph on the same vertex set $V$ . Does there always exist a partition of $V$ into $r$ classes $V_1, \dots , V_r$ such that for both $i=1,2$ , at least $r!m_i/r^r -o(m_i)$ hyperedges of $H_i$ meet each of the classes $V_1, \dots , V_r$ ?

Keywords:

Posted by fhavet
updated March 6th, 2013

add new comment

Graph Theory » Extremal G.T.

Complexity of the H-factor problem. ★★

Author(s): Kühn; Osthus

An $H$ -factor in a graph $G$ is a set of vertex-disjoint copies of $H$ covering all vertices of $G$ .

Problem Let $c$ be a fixed positive real number and $H$ a fixed graph. Is it NP-hard to determine whether a graph $G$ on $n$ vertices and minimum degree $cn$ contains and $H$ -factor?

Keywords:

Posted by fhavet
updated March 5th, 2013

add new comment

Graph Theory » Basic G.T.

Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

Conjecture For all positive integers $g$ and $k$ , there exists an integer $d$ such that every graph of average degree at least $d$ contains a subgraph of average degree at least $k$ and girth greater than $g$ .

Keywords:

Posted by fhavet
updated March 5th, 2013

add new comment

Graph Theory

Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family ${\cal F}$ of graphs and an integer $n$ , the Turán number $ex(n,{\cal F})$ of ${\cal F}$ is the largest integer $m$ such that there exists a graph on $n$ vertices with $m$ edges which contains no member of ${\cal F}$ as a subgraph.

Conjecture For every finite family ${\cal F}$ of graphs there exists an $F\in {\cal F}$ such that $ex(n, F ) = O(ex(n, {\cal F}))$ .

Keywords:

Posted by fhavet
updated March 5th, 2013

add new comment

Graph Theory » Directed Graphs

Subdivision of a transitive tournament in digraphs with large outdegree. ★★

Author(s): Mader

Conjecture For all $k$ there is an integer $f(k)$ such that every digraph of minimum outdegree at least $f(k)$ contains a subdivision of a transitive tournament of order $k$ .

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Topological G.T.

Large induced forest in a planar graph. ★★

Author(s): Abertson; Berman

Conjecture Every planar graph on $n$ verices has an induced forest with at least $n/2$ vertices.

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

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 » Basic G.T. » Paths

Partition of a cubic 3-connected graphs into paths of length 2. ★★

Author(s): Kelmans

Problem Does every $3$ -connected cubic graph on $3k$ vertices admit a partition into $k$ paths of length $2$ ?

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. ★★

Author(s): Sabidussi

Conjecture Let $G$ be an eulerian graph of minimum degree $4$ , and let $W$ be an eulerian tour of $G$ . Then $G$ admits a decomposition into cycles none of which contains two consecutive edges of $W$ .

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

Conjecture Every simple eulerian graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n-1)$ cycles.

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Basic G.T. » Paths

Decomposing a connected graph into paths. ★★★

Author(s): Gallai

Conjecture Every simple connected graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n+1)$ paths.

Keywords:

Posted by fhavet
updated March 4th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Melnikov's valency-variety problem ★

Author(s): Melnikov

Problem The valency-variety $w(G)$ of a graph $G$ is the number of different degrees in $G$ . Is the chromatic number of any graph $G$ with at least two vertices greater than $\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$