Recent Activity

Chromatic number of $\frac{3}{3}$-power of graph ★★

Author(s):

Let $G$ be a graph and $m,n\in \mathbb{N}$ . The graph $G^{\frac{m}{n}}$ is defined to be the $m$ -power of the $n$ -subdivision of $G$ . In other words, $G^{\frac{m}{n}}=(G^{\frac{1}{n}})^m$ .

Conjecture Let $G$ be a graph with $\Delta(G)\geq 2$ . Then $\chi(G^{\frac{3}{3}})\leq 2\Delta(G)+1$ .

Keywords:

Posted by Iradmusa
updated April 20th, 2023

add new comment

Graph Theory

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

Posted by arthur
updated June 23rd, 2022

4 comments

Graph Theory » Basic G.T. » Cycles

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

Posted by Robert Samal
updated June 20th, 2022

3 comments

Geometry

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.

Keywords: complete geometric graph, edge colouring

Posted by David Wood
updated January 6th, 2022

1 comment

Topology

Smooth 4-dimensional Poincare conjecture ★★★★

Author(s): Poincare; Smale; Stallings

Conjecture If a $4$ -manifold has the homotopy type of the $4$ -sphere $S^4$ , is it diffeomorphic to $S^4$ ?

Keywords: 4-manifold; poincare; sphere

Posted by rybu
updated August 26th, 2021

1 comment

Graph Theory

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

Posted by David Wood
updated July 10th, 2021

1 comment

Number Theory

Primitive pythagorean n-tuple tree ★★

Author(s):

Conjecture Find linear transformation construction of primitive pythagorean n-tuple tree!

Keywords:

Posted by tsihonglau
updated June 16th, 2021

1 comment

Geometry » Algebraic Geometry

Jacobian Conjecture ★★★

Author(s): Keller

Conjecture Let $k$ be a field of characteristic zero. A collection $f_1,\ldots,f_n$ of polynomials in variables $x_1,\ldots,x_n$ defines an automorphism of $k^n$ if and only if the Jacobian matrix is a nonzero constant.

Keywords: Affine Geometry; Automorphisms; Polynomials

Posted by Charles
updated March 4th, 2021

1 comment

Topology

Inscribed Square Problem ★★

Author(s): Toeplitz

Conjecture Does every Jordan curve have 4 points on it which form the vertices of a square?

Keywords: simple closed curve; square

Posted by dlh12
updated February 25th, 2021

8 comments

Graph Theory » Basic G.T.

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem Let $G$ be a perfect graph on $n$ vertices. Is it true that either $G$ or $\bar{G}$ contains a complete bipartite subgraph with bipartition $(A,B)$ so that $|A|, |B| \ge n^{1 - o(1)}$ ?

Keywords: perfect graph

Posted by mdevos
updated January 19th, 2021

1 comment

Combinatorics

Transversal achievement game on a square 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 a set of $n$ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

Posted by Martin Erickson
updated January 6th, 2021

3 comments

Graph Theory » Coloring » Labeling

Graceful Tree Conjecture ★★★

Author(s):

Conjecture All trees are graceful

Keywords: combinatorics; graceful labeling

Posted by kintali
updated November 29th, 2020

13 comments

Graph Theory » Extremal G.T.

Extremal problem on the number of tree endomorphism ★★

Author(s): Zhicong Lin

Conjecture An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the $n$ vertices' trees, the star with $n$ vertices has the most endomorphisms, while the path with $n$ vertices has the least endomorphisms.

Keywords:

Posted by shudeshijie
updated November 25th, 2020

3 comments

Graph Theory » Topological G.T. » Coloring

3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set $S$ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $S$ 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 $3$ -colourable.

Keywords: arrangement graph; graph coloring

Posted by David Wood
updated October 22nd, 2020

2 comments

Probability

KPZ Universality Conjecture ★★★

Author(s):

Conjecture Formulate a central limit theorem for the KPZ universality class.

Keywords: KPZ equation, central limit theorem

Posted by Tomas Kojar
updated October 3rd, 2020

add new comment

Graph Theory » Basic G.T.

Friendly partitions ★★

Author(s): DeVos

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

Problem Is it true that for every $r$ , all but finitely many $r$ -regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

Posted by mdevos
updated August 5th, 2020

1 comment

Logic » Finite Model Theory

Finite entailment of Positive Horn logic ★★

Author(s): Martin

Question Positive Horn logic (pH) is the fragment of FO involving exactly $\exists, \forall, \wedge, =$ . Does the fragment $pH \wedge \neg pH$ have the finite model property?

Keywords: entailment; finite satisfiability; horn logic

Posted by LucSegoufin
updated June 15th, 2020

1 comment

Graph Theory » Algebraic G.T.

Triangle free strongly regular graphs ★★★

Author(s):

Problem Is there an eighth triangle free strongly regular graph?

Keywords: strongly regular; triangle free

Posted by mdevos
updated May 30th, 2020

4 comments

Number Theory

A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture Let $a > b > 0$ be integers. Set $b_1 = b$ and $b_{i+1} = {a \bmod {b_i}}$ for $i \geq 0$ . Eventually we have $b_{n+1} = 0$ ; put $P(a,b) = n$ .

Example: $P(35, 22) = 7$ , since $b_1 = 22$ , $b_2 = 13$ , $b_3 = 9$ , $b_4 = 8$ , $b_5 = 3$ , $b_6 = 2$ , $b_7 = 1$ , $b_8 = 0$ .