infinite graph


Characterizing (aleph_0,aleph_1)-graphs ★★★

Author(s): Diestel; Leader

Call a graph an $(\aleph_0,\aleph_1)$-\emph{graph} if it has a bipartition $(A,B)$ so that every vertex in $A$ has degree $\aleph_0$ and every vertex in $B$ has degree $\aleph_1$.

\begin{problem} Characterize the $(\aleph_0,\aleph_1)$-graphs. \end{problem}

Keywords: binary tree; infinite graph; normal spanning tree; set theory

Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

\begin{conjecture} If $G$ is a highly arc transitive digraph with two ends, then every tile of $G$ is a disjoint union of complete bipartite graphs. \end{conjecture}

Keywords: arc transitive; digraph; infinite graph

Strong matchings and covers ★★★

Author(s): Aharoni

Let $H$ be a \Def{hypergraph}. A \emph{strongly maximal} matching is a matching $F \subseteq E(H)$ so that $|F' \setminus F| \le |F \setminus F'|$ for every matching $F'$. A \emph{strongly minimal} cover is a (vertex) cover $X \subseteq V(H)$ so that $|X' \setminus X| \ge |X \setminus X'|$ for every cover $X'$.

\begin{conjecture} If $H$ is a (possibly infinite) hypergraph in which all edges have size $\le k$ for some integer $k$, then $H$ has a strongly maximal matching and a strongly minimal cover. \end{conjecture}

Keywords: cover; infinite graph; matching

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $G$ is a graph, we say that a partition of $V(G)$ is \emph{unfriendly} if every vertex has at least as many neighbors in the other classes as in its own.

\begin{problem} Does every countably infinite graph have an unfriendly partition into two sets? \end{problem}

Keywords: coloring; infinite graph; partition

Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

\begin{conjecture} \begin{enumerate} \item If $G$ is a countable connected graph then its third \Def[power]{Glossary_of_graph_theory#Distance} is hamiltonian. \item If $G$ is a 2-connected countable graph then its square is hamiltonian. \end{enumerate} \end{conjecture}

Keywords: hamiltonian; infinite graph

Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

\begin{conjecture} \begin{enumerate} \item If $G$ is a 4-edge-connected locally finite graph, then its \Def{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. \end{enumerate} \end{conjecture}

Keywords: hamiltonian; infinite graph; line graphs

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

\begin{problem} Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $r > 2$? \end{problem}

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

\begin{problem} Does there exist a graph with no subgraph isomorphic to $K_4$ which cannot be expressed as a union of $\aleph_0$ triangle free graphs? \end{problem}

Keywords: forbidden subgraph; infinite graph; triangle free

Seymour's self-minor conjecture ★★★

Author(s): Seymour

\begin{conjecture} Every infinite graph is a proper \Def[minor]{minor (graph theory)} of itself. \end{conjecture}

Keywords: infinite graph; minor

Syndicate content