All Questions

Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property: If $c:V(G)\rightarrow [k]$ is a vertex ...

I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that $S\subset V$ is a separator for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i....

Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph? Update ...

The neighbourhood of node $v$ in graph $G$ is the subgraph of $G$ induced by all vertices adjacent to $v$. The number of edges between neighbours divided by the number of pairs of neighbours is ...