Home

Recent Activity

Graph Theory » Basic G.T. » Matchings

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

Posted by mdevos
updated August 30th, 2007
add new comment
Number Theory » Computational N.T.

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:

Posted by maxal
updated August 7th, 2007
add new comment
Number Theory » Computational N.T.

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:

Posted by maxal
updated August 5th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

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

Posted by Agelos
updated August 4th, 2007
add new comment
Graph Theory » Coloring » Vertex coloring

Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment $ c $ of colours to the vertices such that no two arcs receive ordered pairs of colours $ (c_1,c_2) $ and $ (c_2,c_1) $. It is equivalent to a homomorphism of the digraph onto some tournament of order $ k $.

Problem   What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

Posted by Robert Samal
updated August 4th, 2007
add new comment
Number Theory » Combinatorial N.T.

Covering systems with big moduli ★★

Author(s): Erdos; Selfridge

Problem   Does for every integer $ N $ exist a covering system with all moduli distinct and at least equal to~$ N $?

Keywords: covering system

Posted by Robert Samal
updated August 4th, 2007
add new comment
Number Theory » Combinatorial N.T.

Odd incongruent covering systems ★★★

Author(s): Erdos; Selfridge

Conjecture   There is no covering system whose moduli are odd, distinct, and greater than 1.

Keywords: covering system

Posted by Robert Samal
updated August 4th, 2007
add new comment
Graph Theory » Infinite Graphs

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

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Infinite Graphs

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

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Basic G.T. » Cycles

Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

Conjecture   Every 4-connected line graph is hamiltonian.

Keywords: hamiltonian; line graphs

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Infinite Graphs

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

Problem   Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $ r > 2 $?

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

Posted by Robert Samal
updated July 24th, 2007
add new comment
Theoretical Comp. Sci. » Complexity

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

Author(s): Regan

Problem   Can $ O(n) $-size circuits compute the function $ f $ on $ \{0,1,2\}^* $ defined inductively by $ f(\lambda) = \lambda $, $ f(0x) = 0f(x) $, $ f(1x) = 1f(x) $, and $ f(2x) = f(x)2 $?

Keywords: Circuits; sorting

Posted by KWRegan
updated July 19th, 2007
add new comment
Theoretical Comp. Sci. » Complexity » Derandomization

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

Posted by ormeir
updated July 16th, 2007
add new comment
Theoretical Comp. Sci. » Complexity

Subset-sums equality (pigeonhole version) ★★★

Author(s):

Problem   Let $ a_1,a_2,\ldots,a_n $ be natural numbers with $ \sum_{i=1}^n a_i < 2^n - 1 $. It follows from the pigeon-hole principle that there exist distinct subsets $ I,J \subseteq \{1,\ldots,n\} $ with $ \sum_{i \in I} a_i = \sum_{j \in J} a_j $. Is it possible to find such a pair $ I,J $ in polynomial time?

Keywords: polynomial algorithm; search problem

Posted by mdevos
updated July 16th, 2007
10 comments
Graph Theory » Coloring » Homomorphisms

Weak pentagon problem ★★

Author(s): Samal

Conjecture   If $ G $ is a cubic graph not containing a triangle, then it is possible to color the edges of $ G $ by five colors, so that the complement of every color class is a bipartite graph.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

Posted by Robert Samal
updated July 13th, 2007
add new comment
Number Theory

Lonely runner conjecture ★★★

Author(s): Cusick; Wills

Conjecture   Suppose $ k $ runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least $ \frac{1}{k} $ (along the track) away from every other runner.

Keywords: diophantine approximation; view obstruction

Posted by mdevos
updated June 24th, 2007
add new comment
Graph Theory » Coloring » Homomorphisms

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture   Every planar graph of girth $ \ge 4k $ has a homomorphism to $ C_{2k+1} $.

Keywords: girth; homomorphism; planar graph

Posted by mdevos
updated June 24th, 2007
add new comment
Graph Theory » Topological G.T. » Coloring

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

Posted by mdevos
updated June 22nd, 2007
add new comment
Combinatorics » Ramsey Theory

Concavity of van der Waerden numbers ★★

Author(s): Landman

For $ k $ and $ \ell $ positive integers, the (mixed) van der Waerden number $ w(k,\ell) $ is the least positive integer $ n $ such that every (red-blue)-coloring of $ [1,n] $ admits either a $ k $-term red arithmetic progression or an $ \ell $-term blue arithmetic progression.

Conjecture   For all $ k $ and $ \ell $ with $ k \geq \ell $, $ w(k,\ell) \geq w(k+1,\ell-1) $.

Keywords: arithmetic progression; van der Waerden

Posted by Bruce Landman
updated June 21st, 2007
add new comment
Graph Theory » Coloring » Vertex coloring

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

Posted by mdevos
updated June 20th, 2007
add new comment