# All Questions

Tagged with graph-theory infinite-combinatorics

56
questions

**3**

votes

**0**answers

31 views

### Generalization of Menger's Theorem to Infinite Graphs

Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets A and B, there is a family F of disjoint paths from A to B and a set separating B from A consisting ...

**1**

vote

**1**answer

38 views

### Induced subgraphs of the line graph of a dense linear hypergraph

Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$
We ...

**3**

votes

**2**answers

108 views

### Avoiding multiply covered vertices in graph edge coverings

Let $G=(V,E)$ be a simple, undirected graph with $\bigcup = E$ (that is, there are no isolated vertices). We say that $C\subseteq E$ is an edge cover of $G$ if $\bigcup C = V$. For any edge cover $C$ ...

**0**

votes

**0**answers

31 views

### Giant component in continuum random graph

Is there some similar statement to Giant component theorem for the infinite graph (particularly with continuum vertices)?

**3**

votes

**1**answer

68 views

### Induced subgraphs of $\text{Exp}(G, K_2)$

If $G, H$ are simple, undirected graphs, we define the exponential graph $\text{Exp}(G,H)$ to be the following graph:
the vertex set is the set of all maps $f:V(G)\to V(H)$
two maps $f\neq g: V(G)\to ...

**2**

votes

**1**answer

117 views

### Chromatic number of the linear graph on $[\omega]^\omega$

Let $[\omega]^\omega$ denote the set of infinite subsets of $\omega$. Let $$E = \{\{a,b\}: a,b\in [\omega]^\omega\text{ and } |a\cap b| = 1\}.$$
It is clear that $G = ([\omega]^\omega, E)$ has no ...

**1**

vote

**1**answer

77 views

### Maximizing “happy” vertices in splitting an infinite graph

This question is motivated by a real life task (which is briefly described after the question.)
Let $G=(V,E)$ be an infinite graph. For $v\in V$ let $N(v) = \{x\in V: \{v,x\}\in E\}$. If $S\subseteq ...

**4**

votes

**1**answer

175 views

### Graphs with minimum degree $\delta(G)\lt\aleph_0$

Let $G=(V,E)$ be a graph with minimum degree $\delta(G)=n\lt\aleph_0$. Does $G$ necessarily have a spanning subgraph $G'=(V,E')$ which also has minimum degree $\delta(G')=n$ and is minimal with that ...

**0**

votes

**1**answer

35 views

### Connected subgraph of infinite graph with surjective homormophism, but no graph isomorphism

For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$.
What is an example of a connected graph $G=(V,E)$ and a subset $S\subseteq V$ such that the subgraph $$G[S]:=(S, E\cap [S]^2)$$ is ...

**0**

votes

**1**answer

74 views

### Linear intersection number and chromatic number for infinite graphs

Given a hypergraph $H=(V,E)$ we let its intersection graph $I(H)$ be defined by $V(I(H)) = E$ and $E(I(H)) = \{\{e,e'\}: (e\neq e'\in E) \land (e\cap e'\neq \emptyset)\}$.
A linear hypergraph is a ...

**0**

votes

**1**answer

37 views

### Minimizing the set of “faulty” edges in a map between the vertex sets of $2$ graphs

The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.
...

**1**

vote

**1**answer

43 views

### Tightly knit graphs on $\omega$

We say that a simple, undirected graph $G = (\omega, E)$ on the vertex set $\omega$ is tightly knit if there is a positive integer $n>2$ such that for all $v,w\in \omega$ there is a cycle $C$ of ...

**3**

votes

**1**answer

209 views

### Does every directed graph have a directed coloring with $4$ colors?

Every finite directed graph has a majority coloring with $4$ colors. (The notion of majority coloring is defined below.)
Question. Can every infinite directed graph be majority-colored with $4$ ...

**5**

votes

**1**answer

103 views

### Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?

Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ ...

**0**

votes

**1**answer

132 views

### Is every finite graph an induced minor of $\omega^2$?

Let $G=(V,E)$ be a simple, undirected graph. Suppose that ${\cal S}$ is a collection of non-empty, connected, and pairwise disjoint subsets of $V$. Let $G({\cal S})$ be the graph with vertex set ${\...