# infinite graph

## Characterizing (aleph_0,aleph_1)-graphs ★★★

Call a graph an -*graph* if it has a bipartition so that every vertex in has degree and every vertex in has degree .

**Problem**Characterize the -graphs.

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

## Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

**Conjecture**If is a highly arc transitive digraph with two ends, then every tile of is a disjoint union of complete bipartite graphs.

Keywords: arc transitive; digraph; infinite graph

## Strong matchings and covers ★★★

Author(s): Aharoni

Let be a hypergraph. A *strongly maximal* matching is a matching so that for every matching . A *strongly minimal* cover is a (vertex) cover so that for every cover .

**Conjecture**If is a (possibly infinite) hypergraph in which all edges have size for some integer , then has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

## Unfriendly partitions ★★★

If is a graph, we say that a partition of is *unfriendly* if every vertex has at least as many neighbors in the other classes as in its own.

**Problem**Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

## Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

**Conjecture**

- \item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.

Keywords: hamiltonian; infinite graph

## Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

**Conjecture**

- \item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs

## Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

**Problem**Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree ?

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

## Unions of triangle free graphs ★★★

**Problem**Does there exist a graph with no subgraph isomorphic to which cannot be expressed as a union of triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

## Seymour's self-minor conjecture ★★★

Author(s): Seymour

**Conjecture**Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor