Recent Activity

Forcing a 2-regular minor ★★

Author(s): Reed; Wood

\begin{conjecture} Every graph with average degree at least $\frac{4}{3}t-2$ contains every 2-regular graph on $t$ vertices as a minor. \end{conjecture}

Keywords: minors

Fractional Hadwiger ★★

Author(s): Harvey; Reed; Seymour; Wood

\begin{conjecture} For every graph $G$,\\ (a) $\chi_f(G)\leq\text{had}(G)$\\ (b) $\chi(G)\leq\text{had}_f(G)$\\ (c) $\chi_f(G)\leq\text{had}_f(G)$. \end{conjecture}

Keywords: fractional coloring, minors

Generalized path-connectedness in proximity spaces ★★

Author(s): Porton

Let $\delta$ be a proximity.

A set $A$ is connected regarding $\delta$ iff $\forall X,Y \in \mathscr{P} A \setminus \{ \emptyset \} : \left( X \cup Y = A \Rightarrow X \mathrel{\delta} Y \right)$.

\begin{conjecture} The following statements are equivalent for every endofuncoid $\mu$ and a set $U$: \begin{enumerate} \item $U$ is connected regarding $\mu$. \item For every $a, b \in U$ there exists a totally ordered set $P \subseteq U$ such that $\min P = a$, $\max P = b$, and for every partion $\{ X, Y \}$ of $P$ into two sets $X$, $Y$ such that $\forall x \in X, y \in Y : x < y$, we have $X \mathrel{[ \mu]^{\ast}} Y$. \end{enumerate} \end{conjecture}

Keywords: connected; connectedness; proximity space

Direct proof of a theorem about compact funcoids ★★

Author(s): Porton

\begin{conjecture} Let $f$ is a $T_1$-separable (the same as $T_2$ for symmetric transitive) compact funcoid and $g$ is a uniform space (reflexive, symmetric, and transitive endoreloid) such that $( \mathsf{\tmop{FCD}}) g = f$. Then $g = \langle f \times f \rangle^{\ast} \Delta$. \end{conjecture}

The main purpose here is to find a \emph{direct} proof of this conjecture. It seems that this conjecture can be derived from the well known theorem about existence of exactly one uniformity on a compact set. But that would be what I call an indirect proof, we need a direct proof instead.

The direct proof may be constructed by correcting all errors an omissions in \href[this draft article]{}.

Direct proof could be better because with it we would get a little more general statement like this:

\begin{conjecture} Let $f$ be a $T_1$-separable compact reflexive symmetric funcoid and $g$ be a reloid such that \begin{enumerate} \item $( \mathsf{\tmop{FCD}}) g = f$; \item $g \circ g^{- 1} \sqsubseteq g$. \end{enumerate} Then $g = \langle f \times f \rangle^{\ast} \Delta$. \end{conjecture}

Keywords: compact space; compact topology; funcoid; reloid; uniform space; uniformity

Point sets with no empty pentagon

Author(s): Wood

\begin{problem} Classify the point sets with no empty pentagon. \end{problem}

Keywords: combinatorial geometry; visibility graph

Dirac's Conjecture ★★

Author(s): Dirac

\begin{conjecture} For every set $P$ of $n$ points in the plane, not all collinear, there is a point in $P$ contained in at least $\frac{n}{2}-c$ lines determined by $P$, for some constant $c$. \end{conjecture}

Keywords: point set

Separators in string graphs ★★

Author(s): Fox; Pach; Tóth

\begin{conjecture} Every string graph with $m$ edges has a separator of size $O(\sqrt{m})$. \end{conjecture}

Keywords: separator; string graphs

Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let $S_n$ denote the set of all permutations of $[n]=\set{1,2,\ldots,n}$. Let $i(\pi)$ and $d(\pi)$ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $\pi$. Let $X(\pi)$ denote the set of subsequences of $\pi$ with length at least three. Let $t(\pi)$ denote $\sum_{\tau\in X(\pi)}(i(\tau)+d(\tau))$.

A permutation $\pi\in S_n$ is called a \emph{Roller Coaster permutation} if $t(\pi)=\max_{\tau\in S_n}t(\tau)$. Let $RC(n)$ be the set of all Roller Coaster permutations in $S_n$.

\begin{conjecture} For $n\geq 3$, \begin{itemize} \item If $n=2k$, then $|RC(n)|=4$. \item If $n=2k+1$, then $|RC(n)|=2^j$ with $j\leq k+1$. \end{itemize} \end{conjecture}

\begin{conjecture}[Odd Sum conjecture] Given $\pi\in RC(n)$, \begin{itemize} \item If $n=2k+1$, then $\pi_j+\pi_{n-j+1}$ is odd for $1\leq j\leq k$. \item If $n=2k$, then $\pi_j + \pi_{n-j+1} = 2k+1$ for all $1\leq j\leq k$. \end{itemize} \end{conjecture}


Rota's basis conjecture ★★★

Author(s): Rota

\begin{conjecture} Let $V$ be a vector space of dimension $n$ and let $B_1,\ldots,B_n \subseteq V$ be bases. Then there exist $n$ disjoint transversals of $B_1,\ldots,B_n$ each of which is a base. \end{conjecture}

Keywords: base; latin square; linear algebra; matroid; transversal

Graphs of exact colorings ★★


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


Imbalance conjecture ★★

Author(s): Kozerenko

\begin{conjecture} Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$. Then $M_{G}$ is graphic. \end{conjecture}

Keywords: edge imbalance; graphic sequences

Every metamonovalued reloid is monovalued ★★

Author(s): Porton

\begin{conjecture} Every metamonovalued reloid is monovalued. \end{conjecture}


Every metamonovalued funcoid is monovalued ★★

Author(s): Porton

\begin{conjecture} Every metamonovalued funcoid is monovalued. \end{conjecture}

The reverse is almost trivial: Every monovalued funcoid is metamonovalued.

Keywords: monovalued

Decomposition of completions of reloids ★★

Author(s): Porton

\begin{conjecture} For composable reloids $f$ and $g$ it holds \begin{enumerate} \item $\operatorname{Compl} ( g \circ f) = ( \operatorname{Compl} g) \circ f$ if $f$ is a co-complete reloid; \item $\operatorname{CoCompl} ( f \circ g) = f \circ \operatorname{CoCompl} g$ if $f$ is a complete reloid; \item $\operatorname{CoCompl} ( ( \operatorname{Compl} g) \circ f) = \operatorname{Compl} ( g \circ ( \operatorname{CoCompl} f)) = ( \operatorname{Compl} g) \circ ( \operatorname{CoCompl} f)$; \item $\operatorname{Compl} ( g \circ ( \operatorname{Compl} f)) = \operatorname{Compl} ( g \circ f)$; \item $\operatorname{CoCompl} ( ( \operatorname{CoCompl} g) \circ f) = \operatorname{CoCompl} ( g \circ f)$. \end{enumerate} \end{conjecture}

Keywords: co-completion; completion; reloid

List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

\begin{conjecture} If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$. \end{conjecture}

Keywords: list coloring; Total coloring; total graphs

Partitioning the Projective Plane ★★

Author(s): Noel

Throughout this post, by \emph{projective plane} we mean the set of all lines through the origin in $\mathbb{R}^3$.

\begin{definition} Say that a subset $S$ of the projective plane is \emph{octahedral} if all lines in $S$ pass through the closure of two opposite faces of a regular octahedron centered at the origin. \end{definition}

\begin{definition} Say that a subset $S$ of the projective plane is \emph{weakly octahedral} if every set $S'\subseteq S$ such that $|S'|=3$ is octahedral. \end{definition}

\begin{conjecture} Suppose that the projective plane can be partitioned into four sets, say $S_1,S_2,S_3$ and $S_4$ such that each set $S_i$ is weakly octahedral. Then each $S_i$ is octahedral. \end{conjecture}

Keywords: Partitioning; projective plane

Kriesell's Conjecture ★★

Author(s): Kriesell

\begin{conjecture} Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$. Then $G$ contains $k$ edge-disjoint trees, each of which contains $T$. \end{conjecture}

Keywords: Disjoint paths; edge-connectivity; spanning trees

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

\begin{conjecture} If $G$ is a non-empty graph containing no induced odd cycle of length at least $5$, then there is a $2$-vertex colouring of $G$ in which no maximum clique is monochromatic. \end{conjecture}

Keywords: maximum clique; Partitioning

Almost all non-Hamiltonian 3-regular graphs are 1-connected ★★

Author(s): Haythorpe

\begin{conjecture} Denote by $NH(n)$ the number of non-Hamiltonian 3-regular graphs of size $2n$, and similarly denote by $NHB(n)$ the number of non-Hamiltonian 3-regular 1-connected graphs of size $2n$.

Is it true that $\lim\limits_{n \rightarrow \infty} \displaystyle\frac{NHB(n)}{NH(n)} = 1$? \end{conjecture}

Keywords: Hamiltonian, Bridge, 3-regular, 1-connected

Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

\begin{conjecture} If $G$ is a simple graph which is the union of $k$ pairwise edge-disjoint complete graphs, each of which has $k$ vertices, then the chromatic number of $G$ is $k$. \end{conjecture}

Keywords: chromatic number