# Random

## Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

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

Keywords: hamiltonian; infinite graph; line graphs

## Covering a square with unit squares ★★

Author(s):

Conjecture   For any integer , it is impossible to cover a square of side greater than with unit squares.

Keywords:

## The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

Conjecture   Every graph with maximum degree has chromatic number at most .

Keywords:

## Singmaster's conjecture ★★

Author(s): Singmaster

Conjecture   There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number .

The number appears once in Pascal's triangle, appears twice, appears three times, and appears times. There are infinite families of numbers known to appear times. The only number known to appear times is . It is not known whether any number appears more than times. The conjectured upper bound could be ; Singmaster thought it might be or . See Singmaster's conjecture.

Keywords: Pascal's triangle

## 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

## Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a -connected cubic planar graph can be decomposed into two Hamilton cycles.

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:

## Circular flow number of regular class 1 graphs ★★

Author(s): Steffen

A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .

A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .

Conjecture   Let be an integer and a -regular graph. If is a class 1 graph, then .

## Circular flow numbers of $r$-graphs ★★

Author(s): Steffen

A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and .

A -regular graph is a -graph if for every with odd.

Conjecture   Let be an integer. If is a -graph, then .

Keywords: flow conjectures; nowhere-zero flows

## Jaeger's modular orientation conjecture ★★★

Author(s): Jaeger

Conjecture   Every -edge-connected graph can be oriented so that (mod ) for every vertex .

Keywords: nowhere-zero flow; orientation

## Smooth 4-dimensional Schoenflies problem ★★★★

Author(s): Alexander

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

Keywords: 4-dimensional; Schoenflies; sphere

## 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

## Faithful cycle covers ★★★

Author(s): Seymour

Conjecture   If is a graph, is admissable, and is even for every , then has a faithful cover.

Keywords: cover; cycle

## List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given , what is the smallest integer such that ?

## Strong matchings and covers ★★★

Author(s): Aharoni

Let be a hypergraph. A strongly maximal matching is a matching so that for every matching . A strongly minimal cover is a (vertex) cover so that for every cover .

Conjecture   If is a (possibly infinite) hypergraph in which all edges have size for some integer , then has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

## Seymour's Second Neighbourhood Conjecture ★★★

Author(s): Seymour

Conjecture   Any oriented graph has a vertex whose outdegree is at most its second outdegree.

Keywords: Caccetta-Häggkvist; neighbourhood; second; Seymour

## The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture   The largest measure of a Lebesgue measurable subset of the unit sphere of containing no pair of orthogonal vectors is attained by two open caps of geodesic radius around the north and south poles.

## 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 such that every planar graph has obstacle number at most ?

## 3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question   Is the set of Fibonacci numbers 3-accessible?

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

Author(s): Morrison; Noel

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

## Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

Conjecture   Let be a digraph all of whose strong components are nontrivial. Then contains a cyclic spanning subdigraph with cyclomatic number at most .

Keywords:

## A conjecture about direct product of funcoids ★★

Author(s): Porton

Conjecture   Let and are monovalued, entirely defined funcoids with . Then there exists a pointfree funcoid such that (for every filter on ) (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

## Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere? ★★★

Author(s): Kirby

Problem   Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable.

Keywords: 3-manifold; 4-sphere; embedding

## Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

Problem   Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?

Keywords: polyhedral graphs, distribution

## Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let be an integer and let be a minor minimal clutter with . Then either has a minor for some or has Lehman's property.

Keywords: clutter; covering; MFMC property; packing

## Graphs of exact colorings ★★

Author(s):

Conjecture For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .

Keywords:

## A conjecture on iterated circumcentres ★★

Author(s): Goddyn

Conjecture   Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?

Keywords: periodic; plane geometry; sequence

## 3-Colourability of Arrangements of Great Circles ★★

Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

Conjecture   Every arrangement graph of a set of great circles is -colourable.

Keywords: arrangement graph; graph coloring

## Partition of Complete Geometric Graph into Plane Trees ★★

Author(s):

Conjecture   Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.

## trace inequality ★★

Author(s):

Let be positive semidefinite, by Jensen's inequality, it is easy to see , whenever .

What about the , is it still valid?

Keywords:

## A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture   Let be integers. Set and for . Eventually we have ; put .

Example: , since , , , , , , , .

Prove or disprove: .

Keywords: Pierce expansions

## Lindelöf hypothesis ★★

Author(s): Lindelöf

Conjecture   For any

Since can be replaced by a smaller value, we can also write the conjecture as, for any positive ,

Keywords: Riemann Hypothesis; zeta

## 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

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

Author(s): Sheehan

Conjecture   If is a finite -regular graph, where , then is not uniquely hamiltonian.

Keywords: hamiltonian; regular; uniquely hamiltonian

## Point sets with no empty pentagon ★

Author(s): Wood

Problem   Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

## Monochromatic vertex colorings inherited from Perfect Matchings ★★★

Author(s):

Conjecture   For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?

Keywords:

## 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

## Goldbach conjecture ★★★★

Author(s): Goldbach

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

## Durer's Conjecture ★★★

Author(s): Durer; Shephard

Conjecture   Every convex polytope has a non-overlapping edge unfolding.

Keywords: folding; polytope

## Erdős–Straus conjecture ★★

Author(s): Erdos; Straus

Conjecture

For all , there exist positive integers , , such that .

Keywords: Egyptian fraction

## Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

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

Author(s): Yuster

Conjecture   If is a tournament of order , then it contains arc-disjoint transitive subtournaments of order 3.

Keywords:

## 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

## Subset-sums equality (pigeonhole version) ★★★

Author(s):

Problem   Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?

Keywords: polynomial algorithm; search problem

## 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:

## 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

## Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

Question   Is there a constant such that every -vertex -minor-free graph has at most cliques?

Keywords: clique; graph; minor

## Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

Problem   Can -size circuits compute the function on defined inductively by , , , and ?

Keywords: Circuits; sorting

## Graceful Tree Conjecture ★★★

Author(s):

Conjecture   All trees are graceful

Keywords: combinatorics; graceful labeling

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

Author(s): Harutyunyan

Conjecture   Every planar oriented graph has an acyclic induced subdigraph of order at least .

Keywords: