Search Results

Let $X$ be a non-empty set. Consider $\mathcal{P}(X)$, the power-set of $X$. We say that $a,b \in \mathcal{P}(X)$ form an edge if and only if their symmetric difference is a singleton, i.e. $\textrm{ …

Let $G=(V,E)$ be a simple, undirected graph with the following properties: Contracting any edge increases the chromatic number by $1$; For each minor $M$ of $G$ we have $\chi(M) \leq \chi(G) + 1$. …

We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdos graph if there are $n$ subsets $S_1,\ldots, S_n$ of $V$ such that $V = \bigcup_{n=1}^n S_n$; each $S_k$ has $n$ elements for $k\in\{ …

On the set $[n]:= \{1,\ldots,n\}$ we consider the set $${\cal P}_2([n]) = \big\{\{a,b\}: a,b \in [n], a\neq b\big\}.$$ Since $$|{\cal P}_2([n])| =2^{n \choose 2}$$ there are exactly $2^{n\choose 2}$ …

Given a graph $G$ with $m$ edges, what is the maximum chromatic number $\chi(G)$ that the graph can have? My guess is that $\chi(G) \leq r(m)$ where $r(m) := \max\{k\in \mathbb{N}: \frac{k(k-1)}{2} …

Let $H=(V,E)$ be a hypergraph. If $\kappa$ is a cardinal, we say that a map $c:E\to \kappa$ is an edge coloring if whenever $e_1,e_2\in E$ with $e_1\cap e_2\neq \emptyset$ then $c(e_1)\neq c(e_2)$. Th …

For a finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum degree of $G$, respectively. Is there a constant $K\in\mathbb{N}$ with the following pr …

We say that a finite, simple, undirected graph $G=(V,E)$ is $k$-critical for $k\in\mathbb{N}$ if $\chi(G)=k$ and $\chi(G\setminus \{v\}) = k-1$ for all $v\in V(G)$. Let $\delta(G)$ denote the minimum …

Let $G=(V,E)$ be a finite simple graph. We say a map $p:V\to [n]:=\{1,\ldots,n\}$ is a pseudo-coloring if for all $a\neq b\in[n]$ there is $v\in\psi^{-1}(\{a\})$ and $w\in\psi^{-1}(\{b\})$ such that $ …

Let $G$ be a (finite or infinite) simple graph. We let $\mathrm{Ind}(G)$ be the collection of independent sets. For any cardinal $\kappa$ and coloring map $\chi: G\to \kappa$ we have $\chi^{-1}(\{\bet …

For any set $X$ set $[X]^2 = \big\{\{x,y\}: x,y \in X, x\neq y\big\}$. Suppose $G=(V,E)$ is a simple, undirected graph, let $v^* \notin V$. We let $a(G)$ be the minimal number of edges that we need t …

Let $G=(V,E)$ be a finite, simple, undirected graph. A dominating set is a set $D\subseteq V$ such that for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$. The dominating number $\ …

What is an example of a Hamiltonian graph $G=(V,E)$ such that there is one path visiting all vertices that is not chromatic (definition see below)? Let $G= (V,E)$ be a simple undirected graph on $n …

Question. Is there a finite, simple undirected graph $G=(V,E)$ with more than $1$ vertex such that there is only $1$ coloring bijection (defined below) for $G$? We denote by $\mathbb{N}$ the set of …

Let $G=(V,E)$ be a simple, undirected graph. We call it $k$-critical if $\chi(G)=k$ and removing any vertex decreases the chromatic number. The odd circles $C_{2n+1}$ are all 3-critical. By taking a …