# All Questions

Tagged with graph-theory set-theory

80
questions

**3**

votes

**2**answers

109 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$ ...

**-2**

votes

**2**answers

171 views

### Cardinality of a set of mutually disjoint perfect matchings of $K_\omega$

If $G=(V,E)$ is a simple, undirected graph, we say that $M\subseteq E$ is a perfect matching if the members of $M$ are pairwise disjoint and $\bigcup M = V$. Let $K_\omega$ be the complete graph on $\...

**2**

votes

**1**answer

118 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 ...

**5**

votes

**3**answers

162 views

### Disjunction number of a graph

Let $S\neq \emptyset$ be a set. We make its powerset ${\cal P}(S)$ into a simple, undirected graph by saying that $A, B\in{\cal P}(S)$ form an edge if and only if $A\cap B=\emptyset$.
The ...

**1**

vote

**1**answer

78 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 ...

**1**

vote

**0**answers

71 views

### Generalization of the linear extension theorem to directed acyclic graphs

Using Zorn's lemma one can prove a generalization of the order extension theorem, that states any acyclic digraph is always contained in another acyclic unilaterally connected digraph on the same ...

**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 ...

**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$ ...

**2**

votes

**1**answer

141 views

### Induced minors of $\{0,1\}^\omega$

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 ${\...

**-1**

votes

**1**answer

77 views

### Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**0**

votes

**1**answer

85 views

### Connected infinite graphs in which all matchings are “small”

Is there a countable, simple, connected graph $G=(\omega, E)$ such that $\text{deg}(v)$ is infinite for all $v\in \omega$, and for all matchings $M\subseteq E$ the set $V\setminus (\bigcup M)$ is ...

**12**

votes

**1**answer

390 views

### Is each cover of the plane by lines minimizable?

A cover $\mathcal C$ of a set $X$ by subsets of $X$ is called
$\bullet$ minimal if for every $C\in\mathcal C$ the family $\mathcal C\setminus\{C\}$ is not a cover of $X$;
$\bullet$ minimizable if $\...

**34**

votes

**2**answers

4k views

### How to find Erd?s' treasure trove?

The renowned mathematician, Paul Erd?s, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...

**5**

votes

**1**answer

164 views

### “König's theorem” for $T_2$-spaces?

For any topological space $(X,\tau)$ we define a matching to be a collection of non-empty and pairwise disjoint open sets. We define the matching number $\nu(X,\tau)$ to be the smallest cardinal $\...

**1**

vote

**2**answers

178 views

### Bipartite subgraphs with lots of edges

Suppose $G=(V,E)$ is a simple, undirected graph with $|V|,|E|$ infinite. Is there $B\subseteq E$ with $|B| = |E|$ such that $(V,B)$ is bipartite?