Random

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

Oriented trees in n-chromatic digraphs ★★★

Author(s): Burr

Conjecture   Every digraph with chromatic number at least $ 2k-2 $ contains every oriented tree of order $ k $ as a subdigraph.

Keywords:

Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is $ k $-diregular if every vertex has indegree and outdegree at least $ k $.

Conjecture   For $ d >2 $, every $ d $-diregular oriented graph on at most $ 4d+1 $ vertices has a Hamilton cycle.

Keywords:

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

Wide partition conjecture ★★

Author(s): Chow; Taylor

Conjecture   An integer partition is wide if and only if it is Latin.

Keywords:

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem   Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

Consecutive non-orientable embedding obstructions ★★★

Author(s):

Conjecture   Is there a graph $ G $ that is a minor-minimal obstruction for two non-orientable surfaces?

Keywords: minor; surface

Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

Conjecture   If $ \chi(G)>k $, then $ G $ contains at least $ \frac{(k+1)(k-1)!}{2} $ cycles of length $ 0\bmod k $.

Keywords: chromatic number; cycles

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

Conjecture   Every bridgeless graph has a (5,2)-cycle-cover.

Keywords: cover; cycle

Frobenius number of four or more integers ★★

Author(s):

Problem   Find an explicit formula for Frobenius number $ g(a_1, a_2, \dots, a_n) $ of co-prime positive integers $ a_1, a_2, \dots, a_n $ for $ n\geq 4 $.

Keywords:

Minimal graphs with a prescribed number of spanning trees ★★

Author(s): Azarija; Skrekovski

Conjecture   Let $ n \geq 3 $ be an integer and let $ \alpha(n) $ denote the least integer $ k $ such that there exists a simple graph on $ k $ vertices having precisely $ n $ spanning trees. Then $  \alpha(n) = o(\log{n}). $

Keywords: number of spanning trees, asymptotics

Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let $ S_n $ denote the set of all permutations of $ [n]=\set{1,2,\ldots,n} $. Let $ i(\pi) $ and $ d(\pi) $ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $ \pi $. Let $ X(\pi) $ denote the set of subsequences of $ \pi $ with length at least three. Let $ t(\pi) $ denote $ \sum_{\tau\in X(\pi)}(i(\tau)+d(\tau)) $.

A permutation $ \pi\in S_n $ is called a Roller Coaster permutation if $ t(\pi)=\max_{\tau\in S_n}t(\tau) $. Let $ RC(n) $ be the set of all Roller Coaster permutations in $ S_n $.

Conjecture   For $ n\geq 3 $,
    \item If $ n=2k $, then $ |RC(n)|=4 $. \item If $ n=2k+1 $, then $ |RC(n)|=2^j $ with $ j\leq k+1 $.
Conjecture  (Odd Sum conjecture)   Given $ \pi\in RC(n) $,
    \item If $ n=2k+1 $, then $ \pi_j+\pi_{n-j+1} $ is odd for $ 1\leq j\leq k $. \item If $ n=2k $, then $ \pi_j + \pi_{n-j+1} = 2k+1 $ for all $ 1\leq j\leq k $.

Keywords:

Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let $ r $ be a positive integer. We say that a graph $ G $ is strongly $ r $-colorable if for every partition of the vertices to sets of size at most $ r $ there is a proper $ r $-coloring of $ G $ in which the vertices in each set of the partition have distinct colors.

Conjecture   If $ \Delta $ is the maximal degree of a graph $ G $, then $ G $ is strongly $ 2 \Delta $-colorable.

Keywords: strong coloring

Partial List Coloring ★★★

Author(s): Iradmusa

Let $ G $ be a simple graph, and for every list assignment $ \mathcal{L} $ let $ \lambda_{\mathcal{L}} $ be the maximum number of vertices of $ G $ which are colorable with respect to $ \mathcal{L} $. Define $ \lambda_t = \min{ \lambda_{\mathcal{L}} } $, where the minimum is taken over all list assignments $ \mathcal{L} $ with $ |\mathcal{L}| = t $ for all $ v \in V(G) $.

Conjecture   [2] Let $ G $ be a graph with list chromatic number $ \chi_\ell $ and $ 1\leq r\leq s\leq \chi_\ell $. Then \[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]

Keywords: list assignment; list coloring

Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph $ G $ is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture   $ K_n $ is the only $ n $-chromatic double-critical graph

Keywords: coloring; complete graph

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:

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:

Obstacle number of planar graphs

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some $ k $ such that every planar graph has obstacle number at most $ k $?

Keywords: graph drawing; obstacle number; planar graph; visibility graph

Fractional Hadwiger ★★

Author(s): Harvey; Reed; Seymour; Wood

Conjecture   For every graph $ G $,
(a) $ \chi_f(G)\leq\text{had}(G) $
(b) $ \chi(G)\leq\text{had}_f(G) $
(c) $ \chi_f(G)\leq\text{had}_f(G) $.

Keywords: fractional coloring, minors

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:

Covering powers of cycles with equivalence subgraphs

Author(s):

Conjecture   Given $ k $ and $ n $, the graph $ C_{n}^k $ has equivalence covering number $ \Omega(k) $.

Keywords:

Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

Question   Is the chromatic number of a random lift of $ K_5 $ concentrated on a single value?

Keywords: random lifts, coloring

Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture  
    \item If $ G $ is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph $ L(G) $ of a locally finite graph $ G $ is 4-connected, then $ L(G) $ is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $ G $, let $ s(G) $ ($ s'(G) $) denote the smallest integer $ m $ so that every sequence of $ m $ elements of $ G $ has a subsequence of length $ >0 $ (length $ |G| $) which has product equal to 1 in some order.

Conjecture   $ s'(G) = s(G) + |G| - 1 $ for every finite group $ G $.

Keywords: subsequence sum; zero sum

Linial-Berge path partition duality ★★★

Author(s): Berge; Linial

Conjecture   The minimum $ k $-norm of a path partition on a directed graph $ D $ is no more than the maximal size of an induced $ k $-colorable subgraph.

Keywords: coloring; directed path; partition

Acyclic edge-colouring ★★

Author(s): Fiamcik

Conjecture   Every simple graph with maximum degree $ \Delta $ has a proper $ (\Delta+2) $-edge-colouring so that every cycle contains edges of at least three distinct colours.

Keywords: edge-coloring

Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

Question   Is every proper vertex-minor closed class of graphs chi-bounded?

Keywords: chi-bounded; circle graph; coloring; vertex minor

Diophantine quintuple conjecture ★★

Author(s):

Definition   A set of m positive integers $ \{a_1, a_2, \dots, a_m\} $ is called a Diophantine $ m $-tuple if $ a_i\cdot a_j + 1 $ is a perfect square for all $ 1 \leq i < j \leq m $.
Conjecture  (1)   Diophantine quintuple does not exist.

It would follow from the following stronger conjecture [Da]:

Conjecture  (2)   If $ \{a, b, c, d\} $ is a Diophantine quadruple and $ d > \max \{a, b, c\} $, then $ d = a + b + c + 2bc + 2\sqrt{(ab+1)(ac+1)(bc+1)}. $

Keywords:

Characterizing (aleph_0,aleph_1)-graphs ★★★

Author(s): Diestel; Leader

Call a graph an $ (\aleph_0,\aleph_1) $-graph if it has a bipartition $ (A,B) $ so that every vertex in $ A $ has degree $ \aleph_0 $ and every vertex in $ B $ has degree $ \aleph_1 $.

Problem   Characterize the $ (\aleph_0,\aleph_1) $-graphs.

Keywords: binary tree; infinite graph; normal spanning tree; set theory

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

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

$C^r$ Stability Conjecture ★★★★

Author(s): Palis; Smale

Conjecture   Any $ C^r $ structurally stable diffeomorphism is hyperbolic.

Keywords: diffeomorphisms,; dynamical systems

Fundamental group torsion for subsets of Euclidean 3-space ★★

Author(s): Ancient/folklore

Problem   Does there exist a subset of $ \mathbb R^3 $ such that its fundamental group has an element of finite order?

Keywords: subsets of euclidean space; torsion

Is Skewes' number e^e^e^79 an integer? ★★

Author(s):

Conjecture  

Skewes' number $ e^{e^{e^{79}}} $ is not an integer.

Keywords:

The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

Conjecture   Every graph with maximum degree $ \Delta \geq 9 $ has chromatic number at most $ \max\{\Delta-1, \omega\} $.

Keywords:

Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

Problem   Find $ \lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| } $.

Keywords: coloring; Lieb's Ice Constant; tiling; torus

5-local-tensions ★★

Author(s): DeVos

Conjecture   There exists a fixed constant $ c $ (probably $ c=4 $ suffices) so that every embedded (loopless) graph with edge-width $ \ge c $ has a 5-local-tension.

Keywords: coloring; surface; tension

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:

Nonrepetitive colourings of planar graphs ★★

Author(s): Alon N.; Grytczuk J.; Hałuszczak M.; Riordan O.

Question   Do planar graphs have bounded nonrepetitive chromatic number?

Keywords: nonrepetitive colouring; planar graphs

Dirac's Conjecture ★★

Author(s): Dirac

Conjecture   For every set $ P $ of $ n $ points in the plane, not all collinear, there is a point in $ P $ contained in at least $ \frac{n}{2}-c $ lines determined by $ P $, for some constant $ c $.

Keywords: point set

Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture   If $ G $ is a $ k $-chromatic graph on at most $ mk $ vertices, then $ \text{ch}(G)\leq \text{ch}(K_{m*k}) $.

Keywords: choosability; complete multipartite graph; list coloring

Smooth 4-dimensional Schoenflies problem ★★★★

Author(s): Alexander

Problem   Let $ M $ be a $ 3 $-dimensional smooth submanifold of $ S^4 $, $ M $ diffeomorphic to $ S^3 $. By the Jordan-Brouwer separation theorem, $ M $ separates $ S^4 $ into the union of two compact connected $ 4 $-manifolds which share $ M $ as a common boundary. The Schoenflies problem asks, are these $ 4 $-manifolds diffeomorphic to $ D^4 $? ie: is $ M $ unknotted?

Keywords: 4-dimensional; Schoenflies; sphere

Geodesic cycles and Tutte's Theorem ★★

Author(s): Georgakopoulos; Sprüssel

Problem   If $ G $ is a $ 3 $-connected finite graph, is there an assignment of lengths $ \ell: E(G) \to \mathb R^+ $ to the edges of $ G $, such that every $ \ell $-geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles

Monadic second-order logic with cardinality predicates ★★

Author(s): Courcelle

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:

    \item $ \text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''} $ \item $ \text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''} $

where $ A $ is a fixed recursive set of integers.

Let us fix $ k $ and a closed formula $ F $ in this language.

Conjecture   Is it true that the validity of $ F $ for a graph $ G $ of tree-width at most $ k $ can be tested in polynomial time in the size of $ G $?

Keywords: bounded tree width; cardinality predicates; FMT03-Bedlewo; MSO

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree $ \Delta $ has chromatic number at most $ \ceil{\frac{\Delta}{2}}+2 $.

Keywords: chromatic number; girth; maximum degree; triangle free

Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question  

Is there an algorithm that decides, for input graphs $ G $ and $ H $, whether there exists a homomorphism from $ G $ to $ H $ in time $ O(c^{|V(G)|+|V(H)|}) $ for some constant $ c $?

Keywords: algorithm; Exponential-time algorithm; homomorphism

Ryser's conjecture ★★★

Author(s): Ryser

Conjecture   Let $ H $ be an $ r $-uniform $ r $-partite hypergraph. If $ \nu $ is the maximum number of pairwise disjoint edges in $ H $, and $ \tau $ is the size of the smallest set of vertices which meets every edge, then $ \tau \le (r-1) \nu $.

Keywords: hypergraph; matching; packing

Slice-ribbon problem ★★★★

Author(s): Fox

Conjecture   Given a knot in $ S^3 $ which is slice, is it a ribbon knot?

Keywords: cobordism; knot; ribbon; slice

What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★

Author(s): Goldengorin

We are given a complete simple undirected weighted graph $ G_1=(V,E) $ and its first arbitrary shortest spanning tree $ T_1=(V,E_1) $. We define the next graph $ G_2=(V,E\setminus E_1) $ and find on $ G_2 $ the second arbitrary shortest spanning tree $ T_2=(V,E_2) $. We continue similarly by finding $ T_3=(V,E_3) $ on $ G_3=(V,E\setminus \cup_{i=1}^{2}E_i) $, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let $ T^{k}=(V,\cup_{i=1}^{k}E_i) $ be the graph obtained as union of all $ k $ disjoint trees.

Question 1. What is the smallest number of disjoint spanning trees creates a graph $ T^{k} $ containing a Hamiltonian path.

Question 2. What is the smallest number of disjoint spanning trees creates a graph $ T^{k} $ containing a shortest Hamiltonian path?

Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees

Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

Conjecture   It has been shown that a $ k $-outerplanar embedding for which $ k $ is minimal can be found in polynomial time. Does a similar result hold for $ k $-edge-outerplanar graphs?

Keywords: planar graph; polynomial algorithm