3
votes
chromatic number of a locally connected graph
There are known bounds to the chromatic number of a graph. In general, if $\Delta$ is the highest degree in the graph and $\chi(G)$ its chromatic number,
$$\chi(G) \leq \Delta + 1$$
If the graph is ...
- 3,468
2
votes
Does there exist an oriented graph with fixed amount of vertices and fixed possible indegree and outdegree?
Solutions for your pair of equations can be found using the theory of diophantine equations.
If you specify your two degree sequences (you specify for each vertex both its outdegree and indegree), you ...
- 4,835
1
vote
Finding a new MST for $G(V,E)$ after connecting a new vertex
This is exactly one step of Prim's algorithm. There we already have a minimum spanning tree of some subset of vertices $V'$ then we consider new vertex $v$ and it's incident edges along with the ...
- 21
1
vote
Simple paths in a graph
There are two paths from a to b, two paths from b to d, and one path from a to d.
Therefore, 2 x 2 + 1 = 5.
- 2,592
1
vote
An interesting Hamiltonian path problem concerning the connectivity of subgraphs
I can only provide some generalizations of X.H. Yue's results for small and large $t$.
For $t=2$, the condition is just a reformulation of "every pair of vertices must have an edge between them&...
- 15k
1
vote
Distance between two vertices picked at random from random graph.
This depends on your random graph model. Peeyush's answer is true for fixed $p$, however in a random graph model, we often take $p \in \Theta(\frac{1}{n})$, then by the same reasoning, sending $n\to \...
- 11
1
vote
How to prove crossing number is 3?
I will try to briefly describe my solution.
Let our graph G be somehow drawn in the plane. The graph $G$ contains two subgraphs with vertices $23157$ and $34157$ isomorphic to $K_5$ and a subgraph $H$...
- 10.8k
Only top scored, non community-wiki answers of a minimum length are eligible