Recent Activity

Crossing numbers and coloring ★★★

Author(s): Albertson

We let $cr(G)$ denote the \Def[crossing number]{crossing number (graph theory)} of a graph $G$.

\begin{conjecture} Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$. \end{conjecture}

Keywords: coloring; complete graph; crossing number

Domination in cubic graphs ★★

Author(s): Reed

\begin{problem} Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$ ? \end{problem}

Keywords: cubic graph; domination

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

\begin{conjecture} Let $H$ be a simple $d$-\Def[uniform]{hypergraph} hypergraph, and assume that every set of $d-1$ points is contained in at most $r$ edges. Then there exists an $r+d-1$-edge-coloring so that any two edges which share $d-1$ vertices have distinct colors. \end{conjecture}

Keywords: edge-coloring; hypergraph; Vizing

Distribution and upper bound of mimic numbers ★★

Author(s): Bhattacharyya


Let the notation $a|b$ denote ''$a$ divides $b$''. The mimic function in number theory is defined as follows [1].

\begin{definition} For any positive integer $\mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i}$ divisible by $\mathcal{D}$, the mimic function, $f(\mathcal{D} | \mathcal{N})$, is given by,

$$ f(\mathcal{D} | \mathcal{N}) = \sum_{i=0}^{n}\mathcal{X}_{i}(\mathcal{M}-\mathcal{D})^{i} $$


By using this definition of mimic function, the mimic number of any non-prime integer is defined as follows [1].

\begin{definition} The number $m$ is defined to be the mimic number of any positive integer $\mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i}$, with respect to $\mathcal{D}$, for the minimum value of which $f^{m}(\mathcal{D} | \mathcal{N}) = \mathcal{D}$. \end{definition}

Given these two definitions and a positive integer $\mathcal{D}$, find the distribution of mimic numbers of those numbers divisible by $\mathcal{D}$.

Again, find whether there is an upper bound of mimic numbers for a set of numbers divisible by any fixed positive integer $\mathcal{D}$. \end{problem}

Keywords: Divisibility; mimic function; mimic number

Coloring random subgraphs ★★

Author(s): Bukh

If $G$ is a graph and $p \in [0,1]$, we let $G_p$ denote a subgraph of $G$ where each edge of $G$ appears in $G_p$ with independently with probability $p$.

\begin{problem} Does there exist a constant $c$ so that ${\mathbb E}(\chi(G_{1/2})) > c \frac{\chi(G)}{\log \chi(G)}$? \end{problem}

Keywords: coloring; random graph

Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

\begin{question} Is every proper vertex-minor closed class of graphs chi-bounded? \end{question}

Keywords: chi-bounded; circle graph; coloring; vertex minor

Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family ${\mathcal F}$ of graphs is $\chi$-\emph{bounded} if there exists a function $f: {\mathbb N} \rightarrow {\mathbb N}$ so that every $G \in {\mathcal F}$ satisfies $\chi(G) \le f (\omega(G))$.

\begin{conjecture} For every fixed tree $T$, the family of graphs with no induced subgraph isomorphic to $T$ is $\chi$-bounded. \end{conjecture}

Keywords: chi-bounded; coloring; excluded subgraph; tree

Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

\begin{problem} Consider the set of all topologically inequivalent polyhedra with $k$ edges. Define a form parameter for a polyhedron as $\beta:= v/(k+2)$ where $v$ is the number of vertices. What is the distribution of $\beta$ for $k \to \infty$? \end{problem}

Keywords: polyhedral graphs, distribution

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

\begin{conjecture} Every sufficiently large plane triangulation $G$ has a dominating set of size $\le \frac{1}{4} |V(G)|$. \end{conjecture}

Keywords: coloring; domination; multigrid; planar graph; triangulation

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

\begin{conjecture} A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: chromatic number; girth; maximum degree; triangle free

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

\begin{conjecture} Every set of $2^{n-2} + 1$ points in the plane in general position contains a subset of $n$ points which form a convex $n$-gon. \end{conjecture}

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

4-flow conjecture ★★★

Author(s): Tutte

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph with no \Def[Petersen]{petersen graph} \Def[minor]{minor (graph theory)} has a \Def[nowhere-zero]{nowhere-zero flows} 4-flow. \end{conjecture}

Keywords: minor; nowhere-zero flow; Petersen graph

Inequality of the means ★★★


\begin{question} Is is possible to pack $n^n$ rectangular $n$-dimensional boxes each of which has side lengths $a_1,a_2,\ldots,a_n$ inside an $n$-dimensional cube with side length $a_1 + a_2 + \ldots a_n$? \end{question}

Keywords: arithmetic mean; geometric mean; Inequality; packing

P vs. PSPACE ★★★

Author(s): Folklore

\begin{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? \end{problem}

Keywords: P; PSPACE; separation; unconditional

Sums of independent random variables with unbounded variance ★★

Author(s): Feige

\begin{conjecture} If $X_1, \dotsc, X_n \geq 0$ are independent random variables with $\mathbb{E}[X_i] \leq \mu$, then $$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$ \end{conjecture}

Keywords: Inequality; Probability Theory; randomness in TCS

Grunbaum's Conjecture ★★★

Author(s): Grunbaum

\begin{conjecture} If $G$ is a simple loopless \Def[triangulation]{triangulation (topology)} of an \Def{orientable surface}, then the dual of $G$ is 3-edge-colorable. \end{conjecture}

Keywords: coloring; surface

Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

\begin{conjecture} For every rational $\epsilon > 0$ and every rational $\Delta$, there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula $I$ on $n$ variables, for some $n$, and $m = \floor{\Delta n}$ clauses drawn uniformly at random from the set of formulas on $n$ variables. Return with probability at least 0.5 (over the instances) that $I$ is \textit{typical} without returning \textit{typical} for \textit{any} instance with at least $(1 - \epsilon)m$ simultaneously satisfiable clauses. \end{conjecture}

Keywords: NP; randomness in TCS; satisfiability

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

\begin{problem} Do there exist non-isomorphic trees which have the same chromatic symmetric function? \end{problem}

Keywords: chromatic polynomial; symmetric function; tree

Shannon capacity of the seven-cycle ★★★


\begin{problem} What is the Shannon capacity of $C_7$? \end{problem}


Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let $G$ be a finite undirected simple graph.

A \emph{$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 \emph{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.

\begin{conjecture} There is a function $f$ such that for every graph $G$, $$\text{bt}(G) \leq f( \text{bt}(G') )\enspace.$$ \end{conjecture}

Keywords: book embedding; book thickness