Home

Recent Activity

Graph Theory » Directed Graphs

Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

Conjecture   If $ G $ is a $ k $-regular directed graph with no parallel arcs, then $ G $ contains a collection of $ {k+1 \choose 2} $ arc-disjoint directed cycles.

Keywords:

Posted by fhavet
updated May 17th, 2013
add new comment
Topology

Jacob Palis Conjecture(Finitude of Attractors)(Dynamical Systems) ★★★★

Author(s):

Conjecture   Let $ Diff^{r}(M) $ be the space of $ C^{r} $ Diffeomorphisms on the connected , compact and boundaryles manifold M and $ \chi^{r}(M) $ the space of $ C^{r} $ vector fields. There is a dense set $ D\subset Diff^{r}(M) $ ($ D\subset \chi^{r}(M) $ ) such that $ \forall f\in D $ exhibit a finite number of attractor whose basins cover Lebesgue almost all ambient space $ M $

This is a very Deep and Hard problem in Dynamical Systems . It present the dream of the dynamicist mathematicians .

Keywords: Attractors , basins, Finite

Posted by Jailton Viana
updated April 24th, 2013
add new comment
Topology

Closing Lemma for Diffeomorphism (Dynamical Systems) ★★★★

Author(s): Charles Pugh

Conjecture   Let $ f\in Diff^{r}(M) $ and $ p\in\omega_{f} $. Then for any neighborhood $ V_{f}\subset Diff^{r}(M) $ there is $ g\in V_{f} $ such that $ p $ is periodic point of $ g $

There is an analogous conjecture for flows ( $ C^{r} $ vector fields . In the case of diffeos this was proved by Charles Pugh for $ r = 1 $. In the case of Flows this has been solved by Sushei Hayahshy for $ r = 1 $ . But in the two cases the problem is wide open for $ r > 1 $

Keywords: Dynamics , Pertubation

Posted by Jailton Viana
updated April 24th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question   Are there graphs for which $ \text{ch}^{\text{OL}}-\text{ch} $ is arbitrarily large?

Keywords: choosability; list coloring; on-line choosability

Posted by jnoel12
updated April 11th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

On-Line Ohba's Conjecture ★★

Author(s): Huang; Wong; Zhu

Conjecture   If $ |V(G)|\leq 2\chi(G) $, then the on-line choice number of $ G $ is equal to $ \chi(G) $.

Keywords: choosability; list coloring; on-line choosability

Posted by jnoel12
updated April 11th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Choice number of complete multipartite graphs with parts of size 4 ★

Author(s):

Question   What is the choice number of $ K_{4*k} $ for general $ k $?

Keywords: choosability; complete multipartite graph; list coloring

Posted by jnoel12
updated April 11th, 2013
add new comment
Graph Theory

Are almost all graphs determined by their spectrum? ★★★

Author(s):

Problem   Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?

Keywords: cospectral; graph invariant; spectrum

Posted by mdevos
updated March 26th, 2013
add new comment
Graph Theory

Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

Conjecture   If $ A $ is the adjacency matrix of a $ d $-regular graph, then there is a symmetric signing of $ A $ (i.e. replace some $ +1 $ entries by $ -1 $) so that the resulting matrix has all eigenvalues of magnitude at most $ 2 \sqrt{d-1} $.

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

Posted by mdevos
updated March 24th, 2013
add new comment
Graph Theory » Extremal G.T.

The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★

Author(s):

Conjecture  (BEC-conjecture)   If $ G_1 $ and $ G_2 $ are $ n $-vertex graphs and $ (\Delta(G_1) + 1) (\Delta(G_2) + 1) < n + 1 $, then $ G_1 $ and $ G_2 $ pack.

Keywords: graph packing

Posted by asp
updated March 23rd, 2013
add new comment
Graph Theory » Directed Graphs » Tournaments

Decomposing k-arc-strong tournament into k spanning strong digraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture   Every k-arc-strong tournament decomposes into k spanning strong digraphs.

Keywords:

Posted by fhavet
updated March 15th, 2013
add new comment
Graph Theory » Graph Algorithms

PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

Question   Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Keywords: feedback arc set; PTAS; tournament

Posted by fhavet
updated March 15th, 2013
add new comment
Graph Theory » Directed Graphs » Tournaments

Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

Problem   Let $ k_1, \dots , k_p $ be positve integer Does there exists an integer $ g(k_1, \dots , k_p) $ such that every $ g(k_1, \dots , k_p) $-strong tournament $ T $ admits a partition $ (V_1\dots , V_p) $ of its vertex set such that the subtournament induced by $ V_i $ is a non-trivial $ k_i $-strong for all $ 1\leq i\leq p $.

Keywords:

Posted by fhavet
updated March 15th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture   There is an absolute constant $ c $ such that for every hexagonal graph $ G $ and vertex weighting $ p:V(G)\rightarrow \mathbb{N} $,
$$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$

Keywords:

Posted by fhavet
updated March 13th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Colouring the square of a planar graph ★★

Author(s): Wegner

Conjecture   Let $ G $ be a planar graph of maximum degree $ \Delta $. The chromatic number of its square is
  • at most $ 7 $ if $ \Delta =3 $,
  • at most $ \Delta+5 $ if $ 4\leq\Delta\leq 7 $,
  • at most $ \left\lfloor\frac32\,\Delta\right\rfloor+1 $ if $ \Delta\ge8 $.

Keywords:

Posted by fhavet
updated March 13th, 2013
add new comment | 1 attachment
Graph Theory » Coloring » Vertex coloring

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture   There is a constant $ c $ such that the list chromatic number of any bipartite graph $ G $ of maximum degree $ \Delta $ is at most $ c \log \Delta $.

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a $ 3 $-connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

Posted by fhavet
updated March 12th, 2013
add new comment
Graph Theory » Hypergraphs

Turán's problem for hypergraphs ★★

Author(s): Turan

Conjecture   Every simple $ 3 $-uniform hypergraph on $ 3n $ vertices which contains no complete $ 3 $-uniform hypergraph on four vertices has at most $ \frac12 n^2(5n-3) $ hyperedges.
Conjecture   Every simple $ 3 $-uniform hypergraph on $ 2n $ vertices which contains no complete $ 3 $-uniform hypergraph on five vertices has at most $ n^2(n-1) $ hyperedges.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

Conjecture   Every $ 4 $-connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Basic G.T. » Cycles

Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture   If $ G $ is a $ 3 $-connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment
Graph Theory » Directed Graphs

Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

Conjecture   Every digraph in which each vertex has outdegree at least $ k $ contains $ k $ directed cycles $ C_1, \ldots, C_k $ such that $ C_j $ meets $ \cup_{i=1}^{j-1}C_i $ in at most one vertex, $ 2 \leq j \leq k $.

Keywords:

Posted by fhavet
updated March 11th, 2013
add new comment