Home

Recent Activity

Graph Theory » Coloring

List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

Conjecture   If $ G $ is the total graph of a multigraph, then $ \chi_\ell(G)=\chi(G) $.

Keywords: list coloring; Total coloring; total graphs

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

Partitioning the Projective Plane ★★

Author(s): Noel

Throughout this post, by projective plane we mean the set of all lines through the origin in $ \mathbb{R}^3 $.

Definition   Say that a subset $ S $ of the projective plane is octahedral if all lines in $ S $ pass through the closure of two opposite faces of a regular octahedron centered at the origin.
Definition   Say that a subset $ S $ of the projective plane is weakly octahedral if every set $ S'\subseteq S $ such that $ |S'|=3 $ is octahedral.
Conjecture   Suppose that the projective plane can be partitioned into four sets, say $ S_1,S_2,S_3 $ and $ S_4 $ such that each set $ S_i $ is weakly octahedral. Then each $ S_i $ is octahedral.

Keywords: Partitioning; projective plane

Posted by Jon Noel
updated August 27th, 2013
add new comment
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
Graph Theory » Basic G.T.

Almost all non-Hamiltonian 3-regular graphs are 1-connected ★★

Author(s): Haythorpe

Conjecture   Denote by $ NH(n) $ the number of non-Hamiltonian 3-regular graphs of size $ 2n $, and similarly denote by $ NHB(n) $ the number of non-Hamiltonian 3-regular 1-connected graphs of size $ 2n $.

Is it true that $ \lim\limits_{n \rightarrow \infty} \displaystyle\frac{NHB(n)}{NH(n)} = 1 $?

Keywords: Hamiltonian, Bridge, 3-regular, 1-connected

Posted by mhaythorpe
updated August 23rd, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

Conjecture   If $ G $ is a simple graph which is the union of $ k $ pairwise edge-disjoint complete graphs, each of which has $ k $ vertices, then the chromatic number of $ G $ is $ k $.

Keywords: chromatic number

Posted by Jon Noel
updated August 22nd, 2013
add new comment
Number Theory » Analytic N.T.

Are there only finite Fermat Primes? ★★★

Author(s):

Conjecture   A Fermat prime is a Fermat number \[ F_n = 2^{2^n } + 1 \] that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.

Keywords:

Posted by kurtulmehtap
updated August 21st, 2013
add new comment
Number Theory » Analytic N.T.

Are all Fermat Numbers square-free? ★★★

Author(s):

Conjecture   Are all Fermat Numbers \[ F_n = 2^{2^{n } } + 1 \] Square-Free?

Keywords:

Posted by kurtulmehtap
updated August 21st, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Choosability of Graph Powers ★★

Author(s): Noel

Question  (Noel, 2013)   Does there exist a function $ f(k)=o(k^2) $ such that for every graph $ G $, \[\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?\]

Keywords: choosability; chromatic number; list coloring; square of a graph

Posted by Jon Noel
updated July 13th, 2013
add new comment
Graph Theory » Directed Graphs

Erdős-Posa property for long directed cycles ★★

Author(s): Havet; Maia

Conjecture   Let $ \ell \geq 2 $ be an integer. For every integer $ n\geq 0 $, there exists an integer $ t_n=t_n(\ell) $ such that for every digraph $ D $, either $ D $ has a $ n $ pairwise-disjoint directed cycles of length at least $ \ell $, or there exists a set $ T $ of at most $ t_n $ vertices such that $ D-T $ has no directed cycles of length at least $ \ell $.

Keywords:

Posted by fhavet
updated June 25th, 2013
add new comment
Graph Theory » Directed Graphs

Large acyclic induced subdigraph in a planar oriented graph. ★★

Author(s): Harutyunyan

Conjecture   Every planar oriented graph $ D $ has an acyclic induced subdigraph of order at least $ \frac{3}{5} |V(D)| $.

Keywords:

Posted by fhavet
updated June 25th, 2013
add new comment
Number Theory

Polignac's Conjecture ★★★

Author(s): de Polignac

Conjecture   Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely many cases of two consecutive prime numbers with difference n.

In particular, this implies:

Conjecture   Twin Prime Conjecture: There are an infinite number of twin primes.

Keywords: prime; prime gap

Posted by Hugh Barker
updated June 18th, 2013
3 comments
Number Theory

Alexa's Conjecture on Primality ★★

Author(s): Alexa

Definition   Let $ r_i $ be the unique integer (with respect to a fixed $ p\in\mathbb{N} $) such that

$$(2i+1)^{p-1} \equiv r_i \pmod p ~~\text{ and } ~ 0 \le r_i < p. $$

Conjecture   A natural number $ p \ge 8 $ is a prime iff $$ \displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor} r_i = \left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor $$

Keywords: primality

Posted by princeps
updated June 14th, 2013
7 comments
Theoretical Comp. Sci. » Complexity » Derandomization

P vs. BPP ★★★

Author(s): Folklore

Conjecture   Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?

Keywords: BPP; circuit complexity; pseudorandom generators

Posted by Charles R Great...
updated June 14th, 2013
add new comment
Number Theory » Additive N.T.

Goldbach conjecture ★★★★

Author(s): Goldbach

Conjecture   Every even integer greater than 2 is the sum of two primes.

Keywords: additive basis; prime

Posted by Benschop
updated June 14th, 2013
3 comments
Graph Theory » Coloring » Edge coloring

Goldberg's conjecture ★★★

Author(s): Goldberg

The overfull parameter is defined as follows: \[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]

Conjecture   Every graph $ G $ satisfies $ \chi'(G) \le \max\{ \Delta(G) + 1, w(G) \} $.

Keywords: edge-coloring; multigraph

Posted by mdevos
updated June 5th, 2013
2 comments
Graph Theory » Directed Graphs

Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

Conjecture   Let $ D $ be a digraph all of whose strong components are nontrivial. Then $ D $ contains a cyclic spanning subdigraph with cyclomatic number at most $ \alpha(D) $.

Keywords:

Posted by fhavet
updated June 2nd, 2013
add new comment
Algebra

inverse of an integer matrix ★★

Author(s): Gregory

Question   I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all $ \ge 2 $. Suppose X is an m-by-n integer matrix $ (m \le n) $. Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

Keywords: invertable matrices, integer matrices

Posted by lvoyster
updated May 27th, 2013
add new comment
Graph Theory

Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament ★★

Author(s): Yuster

Conjecture   If $ T $ is a tournament of order $ n $, then it contains $ \left \lceil n(n-1)/6 - n/3\right\rceil $ arc-disjoint transitive subtournaments of order 3.

Keywords:

Posted by fhavet
updated May 21st, 2013
add new comment
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