# All Questions

Tagged with graph-theory set-theory

78 questions

**2**

votes

**1**answer

109 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

156 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

76 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

67 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

73 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

206 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

138 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

75 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

387 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

3k 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

161 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

172 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?

**3**

votes

**1**answer

170 views

### Infinite graph with lots of non-isomorphic induced subgraphs

Given an infinite cardinal $\kappa$, is there a graph on $\kappa$ vertices that contains $2^\kappa$ pairwise non-isomorphic induced subgraphs?

**8**

votes

**1**answer

395 views

### Does Vizing's conjecture hold for the infinite graphs?

In finite graph theory, there are many (in)equalities which relate the integer value of a certain graph invariant (e.g. domination or chromatic number) for the product of two finite graphs (e.g. ...