Random

Faithful cycle covers ★★★

Author(s): Seymour

Conjecture   If $ G = (V,E) $ is a graph, $ p : E \rightarrow {\mathbb Z} $ is admissable, and $ p(e) $ is even for every $ e \in E(G) $, then $ (G,p) $ has a faithful cover.

Keywords: cover; cycle

3-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every 4-edge-connected graph has a nowhere-zero 3-flow.

Keywords: nowhere-zero flow

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:

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

Sidorenko's Conjecture ★★★

Author(s): Sidorenko

Conjecture   For any bipartite graph $ H $ and graph $ G $, the number of homomorphisms from $ H $ to $ G $ is at least $ \left(\frac{2|E(G)|}{|V(G)|^2}\right)^{|E(H)|}|V(G)|^{|V(H)|} $.

Keywords: density problems; extremal combinatorics; homomorphism

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

Conjecture   Every 6-connected graph without a $ K_6 $ minor is apex (planar plus one vertex).

Keywords: connectivity; minor

Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let $ G $ be a finite undirected simple graph.

A $ k $-page book embedding of $ G $ consists of a linear order $ \preceq $ of $ V(G) $ and a (non-proper) $ k $-colouring of $ E(G) $ such that edges with the same colour do not cross with respect to $ \preceq $. That is, if $ v\prec x\prec w\prec y $ for some edges $ vw,xy\in E(G) $, then $ vw $ and $ xy $ receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The book thickness of $ G $, denoted by bt$ (G) $ is the minimum integer $ k $ for which there is a $ k $-page book embedding of $ G $.

Let $ G' $ be the graph obtained by subdividing each edge of $ G $ exactly once.

Conjecture   There is a function $ f $ such that for every graph $ G $, $$   \text{bt}(G) \leq f( \text{bt}(G') )\enspace.   $$

Keywords: book embedding; book thickness

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation $ G $ has a dominating set of size $ \le \frac{1}{4} |V(G)| $.

Keywords: coloring; domination; multigrid; planar graph; triangulation

3-Edge-Coloring Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Suppose $ G $ with $ |V(G)|>2 $ is a connected cubic graph admitting a $ 3 $-edge coloring. Then there is an edge $ e \in E(G) $ such that the cubic graph homeomorphic to $ G-e $ has a $ 3 $-edge coloring.

Keywords: 3-edge coloring; 4-flow; removable edge

Grunbaum's Conjecture ★★★

Author(s): Grunbaum

Conjecture   If $ G $ is a simple loopless triangulation of an orientable surface, then the dual of $ G $ is 3-edge-colorable.

Keywords: coloring; surface

Saturated $k$-Sperner Systems of Minimum Size ★★

Author(s): Morrison; Noel; Scott

Question   Does there exist a constant $ c>1/2 $ and a function $ n_0(k) $ such that if $ |X|\geq n_0(k) $, then every saturated $ k $-Sperner system $ \mathcal{F}\subseteq \mathcal{P}(X) $ has cardinality at least $ 2^{(1+o(1))ck} $?

Keywords: antichain; extremal combinatorics; minimum saturation; saturation; Sperner system

Unconditional derandomization of Arthur-Merlin games ★★★

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that $ \mathcal{AM} $ $ \subseteq $ $ \Sigma_2 $.

Keywords: Arthur-Merlin; Hitting Sets; unconditional

Convex Equipartitions with Extreme Perimeter ★★

Author(s): Nandakumar

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.

Remark: It appears maximizing the total perimeter is the easier problem.

Keywords: convex equipartition

r-regular graphs are not uniquely hamiltonian. ★★★

Author(s): Sheehan

Conjecture   If $ G $ is a finite $ r $-regular graph, where $ r > 2 $, then $ G $ is not uniquely hamiltonian.

Keywords: hamiltonian; regular; uniquely hamiltonian

Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

Conjecture   Every 4-connected toroidal graph has a Hamilton cycle.

Keywords:

Average diameter of a bounded cell of a simple arrangement ★★

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The average diameter of a bounded cell of a simple arrangement defined by $ n $ hyperplanes in dimension $ d $ is not greater than $ d $.

Keywords: arrangement; diameter; polytope

A conjecture about direct product of funcoids ★★

Author(s): Porton

Conjecture   Let $ f_1 $ and $ f_2 $ are monovalued, entirely defined funcoids with $ \operatorname{Src}f_1=\operatorname{Src}f_2=A $. Then there exists a pointfree funcoid $ f_1 \times^{\left( D \right)} f_2 $ such that (for every filter $ x $ on $ A $) $$\left\langle f_1 \times^{\left( D \right)} f_2 \right\rangle x = \bigcup \left\{ \langle f_1\rangle X \times^{\mathsf{FCD}} \langle f_2\rangle X \hspace{1em} | \hspace{1em} X \in \mathrm{atoms}^{\mathfrak{A}} x \right\}.$$ (The join operation is taken on the lattice of filters with reversed order.)

A positive solution of this problem may open a way to prove that some funcoids-related categories are cartesian closed.

Keywords: category theory; general topology

Upgrading a completary multifuncoid ★★

Author(s): Porton

Let $ \mho $ be a set, $ \mathfrak{F} $ be the set of filters on $ \mho $ ordered reverse to set-theoretic inclusion, $ \mathfrak{P} $ be the set of principal filters on $ \mho $, let $ n $ be an index set. Consider the filtrator $ \left( \mathfrak{F}^n ; \mathfrak{P}^n \right) $.

Conjecture   If $ f $ is a completary multifuncoid of the form $ \mathfrak{P}^n $, then $ E^{\ast} f $ is a completary multifuncoid of the form $ \mathfrak{F}^n $.

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords:

Antichains in the cycle continuous order ★★

Author(s): DeVos

If $ G $,$ H $ are graphs, a function $ f : E(G) \rightarrow E(H) $ is called cycle-continuous if the pre-image of every element of the (binary) cycle space of $ H $ is a member of the cycle space of $ G $.

Problem   Does there exist an infinite set of graphs $ \{G_1,G_2,\ldots \} $ so that there is no cycle continuous mapping between $ G_i $ and $ G_j $ whenever $ i \neq j $ ?

Keywords: antichain; cycle; poset

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

The permanent conjecture ★★

Author(s): Kahn

Conjecture   If $ A $ is an invertible $ n \times n $ matrix, then there is an $ n \times n $ submatrix $ B $ of $ [A A] $ so that $ perm(B) $ is nonzero.

Keywords: invertible; matrix; permanent

57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question   Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph

Twin prime conjecture ★★★★

Author(s):

Conjecture   There exist infinitely many positive integers $ n $ so that both $ n $ and $ n+2 $ are prime.

Keywords: prime; twin prime

Odd perfect numbers ★★★

Author(s): Ancient/folklore

Conjecture   There is no odd perfect number.

Keywords: perfect number

Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

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:

Square achievement game on an n x n grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $ n \times n $ grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

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:

Perfect 2-error-correcting codes over arbitrary finite alphabets. ★★

Author(s):

Conjecture   Does there exist a nontrivial perfect 2-error-correcting code over any finite alphabet, other than the ternary Golay code?

Keywords: 2-error-correcting; code; existence; perfect; perfect code

Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

Conjecture   For every $ \epsilon > 0 $ and every positive integer $ k $, there exists $ r_0 = r_0(\epsilon,k) $ so that every simple $ r $-regular graph $ G $ with $ r \ge r_0 $ has a $ k $-regular subgraph $ H $ with $ |V(H)| \ge (1- \epsilon) |V(G)| $.

Keywords: regular; subgraph

Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

Let $ C $ be a class of finite relational structures. We denote by $ f_C(n) $ the number of structures in $ C $ over the labeled set $ \{0, \dots, n-1 \} $. For any class $ C $ definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every $ m \in \mathbb{N} $, the function $ f_C(n) $ is ultimately periodic modulo $ m $.

Question   Does the Blatter-Specker Theorem hold for ternary relations.

Keywords: Blatter-Specker Theorem; FMT00-Luminy

Cores of strongly regular graphs ★★★

Author(s): Cameron; Kazanidis

Question   Does every strongly regular graph have either itself or a complete graph as a core?

Keywords: core; strongly regular

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

Another conjecture about reloids and funcoids ★★

Author(s): Porton

Definition   $ \square f = \bigcap^{\mathsf{RLD}} \mathrm{up}^{\Gamma (\operatorname{Src} f ; \operatorname{Dst} f)} f $ for reloid $ f $.
Conjecture   $ (\mathsf{RLD})_{\Gamma} f = \square (\mathsf{RLD})_{\mathrm{in}} f $ for every funcoid $ f $.

Note: it is known that $ (\mathsf{RLD})_{\Gamma} f \ne \square (\mathsf{RLD})_{\mathrm{out}} f $ (see below mentioned online article).

Keywords:

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

Snevily's conjecture ★★★

Author(s): Snevily

Conjecture   Let $ G $ be an abelian group of odd order and let $ A,B \subseteq G $ satisfy $ |A| = |B| = k $. Then the elements of $ A $ and $ B $ may be ordered $ A = \{a_1,\ldots,a_k\} $ and $ B = \{b_1,\ldots,b_k\} $ so that the sums $ a_1+b_1, a_2+b_2 \ldots, a_k + b_k $ are pairwise distinct.

Keywords: addition table; latin square; transversal

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:

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:

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to $ K_4 $ which cannot be expressed as a union of $ \aleph_0 $ triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let $ H $ be a simple $ d $-uniform hypergraph, and assume that every set of $ d-1 $ points is contained in at most $ r $ edges. Then there exists an $ r+d-1 $-edge-coloring so that any two edges which share $ d-1 $ vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube ★★

Author(s): Morrison; Noel

Problem   Determine the smallest percolating set for the $ 4 $-neighbour bootstrap process in the hypercube.

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

Conjecture   Every convex polyhedron has a (nonoverlapping) edge unfolding.

Keywords: folding; nets

Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

Conjecture   Let $ G $ be a simple graph with $ n $ vertices and list chromatic number $ \chi_\ell(G) $. Suppose that $ 0\leq t\leq \chi_\ell $ and each vertex of $ G $ is assigned a list of $ t $ colors. Then at least $ \frac{tn}{\chi_\ell(G)} $ vertices of $ G $ can be colored from these lists.

Keywords: list assignment; list coloring

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:

Tarski's exponential function problem ★★

Author(s): Tarski

Conjecture   Is the theory of the real numbers with the exponential function decidable?

Keywords: Decidability

Rota's unimodal conjecture ★★★

Author(s): Rota

Let $ M $ be a matroid of rank $ r $, and for $ 0 \le i \le r $ let $ w_i $ be the number of closed sets of rank $ i $.

Conjecture   $ w_0,w_1,\ldots,w_r $ is unimodal.
Conjecture   $ w_0,w_1,\ldots,w_r $ is log-concave.

Keywords: flat; log-concave; matroid

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $ G $, we let $ \gamma(G) $ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $ \beta(G) $ be the size of the smallest feedback edge set.

Conjecture  If $ G $ is a simple digraph without directed cycles of length $ \le 3 $, then $ \beta(G) \le \frac{1}{2} \gamma(G) $.

Keywords: acyclic; digraph; feedback edge set; triangle free

Vertex Coloring of graph fractional powers ★★★

Author(s): Iradmusa

Conjecture   Let $ G $ be a graph and $ k $ be a positive integer. The $ k- $power of $ G $, denoted by $ G^k $, is defined on the vertex set $ V(G) $, by connecting any two distinct vertices $ x $ and $ y $ with distance at most $ k $. In other words, $ E(G^k)=\{xy:1\leq d_G(x,y)\leq k\} $. Also $ k- $subdivision of $ G $, denoted by $ G^\frac{1}{k} $, is constructed by replacing each edge $ ij $ of $ G $ with a path of length $ k $. Note that for $ k=1 $, we have $ G^\frac{1}{1}=G^1=G $.
Now we can define the fractional power of a graph as follows:
Let $ G $ be a graph and $ m,n\in \mathbb{N} $. The graph $ G^{\frac{m}{n}} $ is defined by the $ m- $power of the $ n- $subdivision of $ G $. In other words $ G^{\frac{m}{n}}\isdef (G^{\frac{1}{n}})^m $.
Conjecture. Let $ G $ be a connected graph with $ \Delta(G)\geq3 $ and $ m $ be a positive integer greater than 1. Then for any positive integer $ n>m $, we have $ \chi(G^{\frac{m}{n}})=\omega(G^\frac{m}{n}) $.
In [1], it was shown that this conjecture is true in some special cases.

Keywords: chromatic number, fractional power of graph, clique number

Fixed-point logic with counting ★★

Author(s): Blass

Question   Can either of the following be expressed in fixed-point logic plus counting:
    \item Given a graph, does it have a perfect matching, i.e., a set $ M $ of edges such that every vertex is incident to exactly one edge from $ M $? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?

Keywords: Capturing PTime; counting quantifiers; Fixed-point logic; FMT03-Bedlewo

Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let $ S $ be a set of points in the plane. Two points $ v $ and $ w $ in $ S $ are visible with respect to $ S $ if the line segment between $ v $ and $ w $ contains no other point in $ S $.

Conjecture   For all integers $ k,\ell\geq2 $ there is an integer $ n $ such that every set of at least $ n $ points in the plane contains at least $ \ell $ collinear points or $ k $ pairwise visible points.

Keywords: Discrete Geometry; Geometric Ramsey Theory