DeVos, Matt


Friendly partitions ★★

Author(s): DeVos

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

\begin{problem} Is it true that for every $r$, all but finitely many $r$-regular graphs have friendly partitions? \end{problem}

Keywords: edge-cut; partition; regular

Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let ${\mathcal O}$ denote the graph with vertex set consisting of all lines through the origin in ${\mathbb R}^3$ and two vertices adjacent in ${\mathcal O}$ if they are perpendicular.

\begin{problem} Is $\chi_c({\mathcal O}) = 4$? \end{problem}

Keywords: circular coloring; geometric graph; orthogonality

5-local-tensions ★★

Author(s): DeVos

\begin{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. \end{conjecture}

Keywords: coloring; surface; tension

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $G$, let $s(G)$ ($s'(G)$) denote the smallest integer $m$ so that every sequence of $m$ elements of $G$ has a subsequence of length $>0$ (length $|G|$) which has product equal to 1 in some order.

\begin{conjecture} $s'(G) = s(G) + |G| - 1$ for every finite group $G$. \end{conjecture}

Keywords: subsequence sum; zero sum

Antichains in the cycle continuous order ★★

Author(s): DeVos

If $G$,$H$ are graphs, a function $f : E(G) \rightarrow E(H)$ is called \emph{cycle-continuous} if the pre-image of every element of the (binary) cycle space of $H$ is a member of the cycle space of $G$.

\begin{problem} Does there exist an infinite set of graphs $\{G_1,G_2,\ldots \}$ so that there is no cycle continuous mapping between $G_i$ and $G_j$ whenever $i \neq j$ ? \end{problem}

Keywords: antichain; cycle; poset

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

\begin{conjecture} Let $G$ be the disjoint union of the graphs $G_1$ and $G_2$ and let $\Sigma$ be a surface. Is it true that every optimal drawing of $G$ on $\Sigma$ has the property that $G_1$ and $G_2$ are disjoint? \end{conjecture}

Keywords: crossing number; surface

What is the largest graph of positive curvature?

Author(s): DeVos; Mohar

\begin{problem} What is the largest connected \Def{planar graph} of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a \Def[prism]{prism (geometry)} or \Def{antiprism}? \end{problem}

Keywords: curvature; planar graph

Partitioning edge-connectivity ★★

Author(s): DeVos

\begin{question} Let $G$ be an $(a+b+2)$-\Def[edge-connected]{connectivity (graph theory)} graph. Does there exist a partition $\{A,B\}$ of $E(G)$ so that $(V,A)$ is $a$-edge-connected and $(V,B)$ is $b$-edge-connected? \end{question}

Keywords: edge-coloring; edge-connectivity

Packing T-joins ★★

Author(s): DeVos

\begin{conjecture} There exists a fixed constant $c$ (probably $c=1$ suffices) so that every graft with minimum $T$-cut size at least $k$ contains a $T$-join packing of size at least $(2/3)k-c$. \end{conjecture}

Keywords: packing; T-join

A homomorphism problem for flows ★★

Author(s): DeVos

\begin{conjecture} Let $M,M'$ be abelian groups and let $B \subseteq M$ and $B' \subseteq M'$ satisfy $B=-B$ and $B' = -B'$. If there is a \Def[homomorphism]{graph homomorphism} from $Cayley(M,B)$ to $Cayley(M',B')$, then every graph with a B-flow has a B'-flow. \end{conjecture}

Keywords: homomorphism; nowhere-zero flow; tension

Syndicate content