# Random

## Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. ★★

Author(s): Sabidussi

**Conjecture**Let be an eulerian graph of minimum degree , and let be an eulerian tour of . Then admits a decomposition into cycles none of which contains two consecutive edges of .

Keywords:

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

**Question**

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

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 is a -connected finite graph, is there an assignment of lengths to the edges of , such that every -geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles

## Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set has *distinct subset sums* if distinct subsets of have distinct sums.

**Conjecture**There exists a fixed constant so that whenever has distinct subset sums.

Keywords: subset sum

## Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

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

Keywords: arc transitive; digraph; infinite graph

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

Author(s): Beneš

**Problem ()**Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?

**Conjecture ()**Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.

Keywords:

## Packing T-joins ★★

Author(s): DeVos

**Conjecture**There exists a fixed constant (probably suffices) so that every graft with minimum -cut size at least contains a -join packing of size at least .

## Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

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

Keywords: planar graph; polynomial algorithm

## Double-critical graph conjecture ★★

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

**Conjecture**is the only -chromatic double-critical graph

Keywords: coloring; complete graph

## Weighted colouring of hexagonal graphs. ★★

**Conjecture**There is an absolute constant such that for every hexagonal graph and vertex weighting ,

Keywords:

## Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

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

**Conjecture**If is the maximal degree of a graph , then is strongly -colorable.

Keywords: strong coloring

## 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 be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

**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 be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

## Circular coloring triangle-free subcubic planar graphs ★★

**Problem**Does every triangle-free planar graph of maximum degree three have circular chromatic number at most ?

Keywords: circular coloring; planar graph; triangle free

## Edge list coloring conjecture ★★★

Author(s):

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

Keywords:

## The intersection of two perfect matchings ★★

**Conjecture**Every bridgeless cubic graph has two perfect matchings , so that 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 is a -chromatic graph on at most vertices, then .

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 (probably suffices) so that every embedded (loopless) graph with edge-width has a 5-local-tension.

## What are hyperfuncoids isomorphic to? ★★

Author(s): Porton

Let be an indexed family of sets.

*Products* are for .

*Hyperfuncoids* are filters on the lattice of all finite unions of products.

**Problem**Is a bijection from hyperfuncoids to:

- \item prestaroids on ; \item staroids on ; \item completary staroids on ?

If yes, is defining the inverse bijection? If not, characterize the image of the function defined on .

Consider also the variant of this problem with the set replaced with the set of complements of elements of the set .

Keywords: hyperfuncoids; multidimensional

## The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

**Conjecture**If is 2-large, then is large.

Keywords: 2-large sets; large sets

## List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

**Conjecture**If is the total graph of a multigraph, then .

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 such that the list chromatic number of any bipartite graph of maximum degree is at most .

Keywords:

## Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

**Conjecture**Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -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 vertices can be decomposed into at most cycles.

Keywords:

## Signing a graph to have small magnitude eigenvalues ★★

**Conjecture**If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .

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

## The Berge-Fulkerson conjecture ★★★★

**Conjecture**If is a bridgeless cubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .

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 and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.

**Question 1**. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.

**Question 2**. What is the smallest number of disjoint spanning trees creates a graph 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 or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .

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 be a sequence of nonnegative integers which strictly decreases until .

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

Keywords: crossing number; crossing sequence

## Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

**Conjecture**

- \item If is a countable connected graph then its third power is hamiltonian. \item If 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 the following inequality holds

Keywords: Inequality

## Unit vector flows ★★

Author(s): Jain

**Conjecture**For every graph without a bridge, there is a flow .

**Conjecture**There exists a map so that antipodal points of 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?

## Decomposing a connected graph into paths. ★★★

Author(s): Gallai

**Conjecture**Every simple connected graph on vertices can be decomposed into at most paths.

Keywords:

## The Two Color Conjecture ★★

Author(s): Neumann-Lara

**Conjecture**If is an orientation of a simple planar graph, then there is a partition of into so that the graph induced by is acyclic for .

## Hoàng-Reed Conjecture ★★★

**Conjecture**Every digraph in which each vertex has outdegree at least contains directed cycles such that meets in at most one vertex, .

Keywords:

## Diophantine quintuple conjecture ★★

Author(s):

**Definition**A set of m positive integers is called a Diophantine -tuple if is a perfect square for all .

**Conjecture (1)**Diophantine quintuple does not exist.

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

**Conjecture (2)**If is a Diophantine quadruple and , then

Keywords:

## The Crossing Number of the Hypercube ★★

The crossing number of is the minimum number of crossings in all drawings of in the plane.

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

**Conjecture**

Keywords: crossing number; hypercube

## Big Line or Big Clique in Planar Point Sets ★★

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

**Conjecture**For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or 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 such that or prove that such integers do not exist.

Keywords:

## F_d versus F_{d+1} ★★★

Author(s): Krajicek

**Problem**Find a constant such that for any there is a sequence of tautologies of depth that have polynomial (or quasi-polynomial) size proofs in depth Frege system but requires exponential size proofs.

Keywords: Frege system; short proof

## Choosability of Graph Powers ★★

Author(s): Noel

**Question (Noel, 2013)**Does there exist a function such that for every graph ,

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