Random

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:

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

Nonseparating planar continuum ★★

Author(s):

Conjecture   Does any path-connected, compact set in the plane which does not separate the plane have the fixed point property?

A set has the fixed point property if every continuous map from it into itself has a fixed point.

Keywords: fixed point

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

Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set $ S \subseteq {\mathbb Z} $ has distinct subset sums if distinct subsets of $ S $ have distinct sums.

Conjecture   There exists a fixed constant $ c $ so that $ |S| \le \log_2(n) + c $ whenever $ S \subseteq \{1,2,\ldots,n\} $ has distinct subset sums.

Keywords: subset sum

Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

Conjecture   If $ G $ is a highly arc transitive digraph with two ends, then every tile of $ G $ is a disjoint union of complete bipartite graphs.

Keywords: arc transitive; digraph; infinite graph

Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

Problem  ($ \dag $)   Find a sufficient condition for a straight $ \ell $-stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ($ \diamond $)   Let $ L $ be a simple regular ordered $ 2 $-stage graph. Suppose that the graph $ L^m $ is externally connected, for some $ m\ge1 $. Then the graph $ L^{2m} $ is rearrangeable.

Keywords:

Packing T-joins ★★

Author(s): DeVos

Conjecture   There exists a fixed constant $ c $ (probably $ c=1 $ suffices) so that every graft with minimum $ T $-cut size at least $ k $ contains a $ T $-join packing of size at least $ (2/3)k-c $.

Keywords: packing; T-join

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

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

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:

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

4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

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

Circular choosability of planar graphs

Author(s): Mohar

Let $ G = (V, E) $ be a graph. If $ p $ and $ q $ are two integers, a $ (p,q) $-colouring of $ G $ is a function $ c $ from $ V $ to $ \{0,\dots,p-1\} $ such that $ q \le |c(u)-c(v)| \le p-q $ for each edge $ uv\in E $. Given a list assignment $ L $ of $ G $, i.e.~a mapping that assigns to every vertex $ v $ a set of non-negative integers, an $ L $-colouring of $ G $ is a mapping $ c : V \to N $ such that $ c(v)\in L(v) $ for every $ v\in V $. A list assignment $ L $ is a $ t $-$ (p,q) $-list-assignment if $ L(v) \subseteq \{0,\dots,p-1\} $ and $ |L(v)| \ge tq $ for each vertex $ v \in V $ . Given such a list assignment $ L $, the graph G is $ (p,q) $-$ L $-colourable if there exists a $ (p,q) $-$ L $-colouring $ c $, i.e. $ c $ is both a $ (p,q) $-colouring and an $ L $-colouring. For any real number $ t \ge 1 $, the graph $ G $ is $ t $-$ (p,q) $-choosable if it is $ (p,q) $-$ L $-colourable for every $ t $-$ (p,q) $-list-assignment $ L $. Last, $ G $ is circularly $ t $-choosable if it is $ t $-$ (p,q) $-choosable for any $ p $, $ q $. The circular choosability (or circular list chromatic number or circular choice number) of G is $$cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$$

Problem   What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

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

Circular coloring triangle-free subcubic planar graphs ★★

Author(s): Ghebleh; Zhu

Problem   Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $ \frac{20}{7} $?

Keywords: circular coloring; planar graph; triangle free

Edge list coloring conjecture ★★★

Author(s):

Conjecture   Let $ G $ be a loopless multigraph. Then the edge chromatic number of $ G $ equals the list edge chromatic number of $ G $.

Keywords:

The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

Conjecture   Every bridgeless cubic graph has two perfect matchings $ M_1 $, $ M_2 $ so that $ M_1 \cap M_2 $ does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

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

P vs. PSPACE ★★★

Author(s): Folklore

Problem   Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?

Keywords: P; PSPACE; separation; unconditional

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

What are hyperfuncoids isomorphic to? ★★

Author(s): Porton

Let $ \mathfrak{A} $ be an indexed family of sets.

Products are $ \prod A $ for $ A \in \prod \mathfrak{A} $.

Hyperfuncoids are filters $ \mathfrak{F} \Gamma $ on the lattice $ \Gamma $ of all finite unions of products.

Problem   Is $ \bigcap^{\mathsf{\tmop{FCD}}} $ a bijection from hyperfuncoids $ \mathfrak{F} \Gamma $ to:
    \item prestaroids on $ \mathfrak{A} $; \item staroids on $ \mathfrak{A} $; \item completary staroids on $ \mathfrak{A} $?

If yes, is $ \operatorname{up}^{\Gamma} $ defining the inverse bijection? If not, characterize the image of the function $ \bigcap^{\mathsf{\tmop{FCD}}} $ defined on $ \mathfrak{F} \Gamma $.

Consider also the variant of this problem with the set $ \Gamma $ replaced with the set $ \Gamma^{\ast} $ of complements of elements of the set $ \Gamma $.

Keywords: hyperfuncoids; multidimensional

The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

Conjecture   If $ A $ is 2-large, then $ A $ is large.

Keywords: 2-large sets; large sets

Petersen coloring conjecture ★★★

Author(s): Jaeger

Conjecture   Let $ G $ be a cubic graph with no bridge. Then there is a coloring of the edges of $ G $ using the edges of the Petersen graph so that any three mutually adjacent edges of $ G $ map to three mutually adjancent edges in the Petersen graph.

Keywords: cubic; edge-coloring; Petersen graph

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

Triangle free strongly regular graphs ★★★

Author(s):

Problem   Is there an eighth triangle free strongly regular graph?

Keywords: strongly regular; triangle free

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:

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

Conjecture   Can the approximation ratio $ O(\sqrt{n}) $ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than $ \mathcal{APX} $-hardness?

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

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:

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

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture   If $ G $ is a bridgeless cubic graph, then there exist 6 perfect matchings $ M_1,\ldots,M_6 $ of $ G $ with the property that every edge of $ G $ is contained in exactly two of $ M_1,\ldots,M_6 $.

Keywords: cubic; perfect matching

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

Counterexamples to the Baillie-PSW primality test ★★

Author(s):

Problem  (1)   Find a counterexample to Baillie-PSW primality test or prove that there is no one.
Problem  (2)   Find a composite $ n\equiv 3 $ or $ 7\pmod{10} $ which divides both $ 2^{n-1} - 1 $ (see Fermat pseudoprime) and the Fibonacci number $ F_{n+1} $ (see Lucas pseudoprime), or prove that there is no such $ n $.

Keywords:

Switching reconstruction conjecture ★★

Author(s): Stanley

Conjecture   Every simple graph on five or more vertices is switching-reconstructible.

Keywords: reconstruction

Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let $ (a_0,a_1,a_2,\ldots,0) $ be a sequence of nonnegative integers which strictly decreases until $ 0 $.

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus $ i $ with $ a_i $ crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture  
    \item If $ G $ is a countable connected graph then its third power is hamiltonian. \item If $ G $ is a 2-connected countable graph then its square is hamiltonian.

Keywords: hamiltonian; infinite graph

Inequality for square summable complex series ★★

Author(s): Retkes

Conjecture   For all $ \alpha=(\alpha_1,\alpha_2,\ldots)\in l_2(\cal{C}) $ the following inequality holds $$\sum_{n\geq 1}|\alpha_n|^2\geq \frac{6}{\pi^2}\sum_{k\geq0}\bigg| \sum_{l\geq0}\frac{1}{l+1}\alpha_{2^k(2l+1)}\bigg|^2 $$

Keywords: Inequality

Unit vector flows ★★

Author(s): Jain

Conjecture   For every graph $ G $ without a bridge, there is a flow $ \phi : E(G) \rightarrow S^2 = \{ x \in {\mathbb R}^3 : |x| = 1 \} $.

Conjecture   There exists a map $ q:S^2 \rightarrow \{-4,-3,-2,-1,1,2,3,4\} $ so that antipodal points of $ S^2 $ receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.

Keywords: nowhere-zero flow

4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

Problem   Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?

Keywords: coloring; girth

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:

The Two Color Conjecture ★★

Author(s): Neumann-Lara

Conjecture   If $ G $ is an orientation of a simple planar graph, then there is a partition of $ V(G) $ into $ \{X_1,X_2\} $ so that the graph induced by $ X_i $ is acyclic for $ i=1,2 $.

Keywords: acyclic; digraph; planar

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:

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:

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

The $ d $-dimensional (hyper)cube $ Q_d $ is the graph whose vertices are all binary sequences of length $ d $, and two of the sequences are adjacent in $ Q_d $ if they differ in precisely one coordinate.

Conjecture   $ \displaystyle \lim  \frac{cr(Q_d)}{4^d} = \frac{5}{32} $

Keywords: crossing number; hypercube

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

Every metamonovalued reloid is monovalued ★★

Author(s): Porton

Conjecture   Every metamonovalued reloid is monovalued.

Keywords:

A sextic counterexample to Euler's sum of powers conjecture ★★

Author(s): Euler

Problem   Find six positive integers $ x_1, x_2, \dots, x_6 $ such that $$x_1^6 + x_2^6 + x_3^6 + x_4^6 + x_5^6 = x_6^6$$ or prove that such integers do not exist.

Keywords:

F_d versus F_{d+1} ★★★

Author(s): Krajicek

Problem   Find a constant $ k $ such that for any $ d $ there is a sequence of tautologies of depth $ k $ that have polynomial (or quasi-polynomial) size proofs in depth $ d+1 $ Frege system $ F_{d+1} $ but requires exponential size $ F_d $ proofs.

Keywords: Frege system; short proof

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