Home » Keyword index

infinite graph


Graph Theory » Infinite Graphs

Characterizing (aleph_0,aleph_1)-graphs ★★★

Author(s): Diestel; Leader

Call a graph an $ (\aleph_0,\aleph_1) $-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 $.

Problem   Characterize the $ (\aleph_0,\aleph_1) $-graphs.

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

Posted by mdevos
updated November 24th, 2011
2 comments
Graph Theory » Infinite Graphs

Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

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.

Keywords: arc transitive; digraph; infinite graph

Posted by mdevos
updated October 29th, 2007
add new comment
Graph Theory » Infinite Graphs

Strong matchings and covers ★★★

Author(s): Aharoni

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

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.

Keywords: cover; infinite graph; matching

Posted by mdevos
updated October 23rd, 2007
add new comment
Graph Theory » Infinite Graphs

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $ G $ is a graph, we say that a partition of $ V(G) $ 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

Posted by mdevos
updated October 22nd, 2007
add new comment
Graph Theory » Infinite Graphs

Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

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

Keywords: hamiltonian; infinite graph

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Infinite Graphs

Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture  
    \item If $ G $ is a 4-edge-connected locally finite graph, then its 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.

Keywords: hamiltonian; infinite graph; line graphs

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Infinite Graphs

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

Problem   Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $ r > 2 $?

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

Posted by Robert Samal
updated July 24th, 2007
add new comment
Graph Theory » Infinite Graphs

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

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?

Keywords: forbidden subgraph; infinite graph; triangle free

Posted by mdevos
updated June 4th, 2007
add new comment
Graph Theory » Infinite Graphs

Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture   Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

Posted by mdevos
updated April 15th, 2010
2 comments
Syndicate content