Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options not deleted
user 4558
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
11
votes
2
answers
3k
views
Algorithm for embedding a graph with metric constraints
Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide …
- 13.2k
7
votes
Accepted
Covering of a graph via independent sets
As has already been pointed out, this is the chromatic number $\chi$. (For example, the assertion that all planar graphs have $ \chi \le 4$ is the famous "Four color theorem.")
You say your graph has …
- 1,446
18
votes
2
answers
1k
views
In an Erdős–Rényi random graph, what is the threshold for the property "every edge is contai...
Let $G(n,p)$ denote the Erdős–Rényi random graph, where $n$ is the number of nodes and $p$ is the probability for each edge. I'm interested in precisely what range of $p$ the random graph has at least …
CommunityBot
- 1
10
votes
2
answers
441
views
Higher-dimensional Fáry's theorem?
Fáry's theorem says that every finite simple planar graph admits a planar embedding with straight line edges.
For which $(k,d)$ is it true that every finite $k$-dimensional simplicial complex embeddab …
- 1,446
20
votes
2
answers
881
views
Is there an analogue of the Erdős–Gallai theorem for simplicial complexes?
The Erdős–Gallai theorem gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph.
In particular $d_1 \ge d_2 \ge \dots \ge d_n$ …
- 1,446
11
votes
Lower bounds for chromatic number of a graph
Lovasz's topological lower bounds on chromatic number were extended by Babson and Kozlov -- they have a series of articles, all available on the arXiv. A nice place to start is "Complexes of Graph Hom …
- 7,857
57
votes
4
answers
15k
views
Connectivity of the Erdős–Rényi random graph
It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is asymptoti …
- 4,713
27
votes
1
answer
3k
views
Monochromatic triangles in every two-coloring of the plane?
An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means …
- 1,318
14
votes
5
answers
663
views
Do there exist sparse graphs with large crossing number?
Does there exist a sequence of graphs $\{ G_n \}$ such that
$G_n$ has $n$ vertices,
the number of edges of $G_n$ is $O(n)$, and
the crossing number of $G_n$ is $\Omega(n)$?
In particular, do rando …
- 6,101
4
votes
0
answers
263
views
What are the best bounds to date on the maximum girth of a cubic graph?
The girth of a graph is the length of its smallest cycle. Studying the maximum possible girth for a $k$-regular graph on $n$ vertices is a very well-studied problem.
In the 1988 paper "Ramanujan grap …
- 7,857
0
votes
Maximum number of different 4-colorings of planar graphs of a given size
For every tree on $n$ vertices, there are exactly $4 \times 3^{n-1}$ $4$-colorings. This follows from the fact that its chromatic polynomial is $t(t-1)^{n-1}$.
(Or by induction since every tree wit …
- 7,857
10
votes
1
answer
455
views
For what range of edge probability does the following property hold for random graphs?
Let $G(n,p)$ denote the Erdős–Rényi model of random graph. For a given function $p = p(n)$ we say that $G \in G(n,p)$ asymptotically almost surely has property $\mathcal{P}$ if
$$\mbox{Pr}[G \mbox{ …
- 6,711
9
votes
Accepted
Clique sizes in a unit disk graph
Yes, a lot is known about this. See Mathew Penrose's book, "Random Geometric Graphs." He discusses subgraph counts for random geometric graphs on distributions with bounded, measurable, density func …
CommunityBot
- 1
4
votes
Generalization or Improvement of Cheeger inequality on Graphs
One place to look might be random graphs $G(n,p)$. This might either give you a wide class of graphs for which an improvement holds, or else show you a limit to what you might hope for.
For Cheeger …
- 7,857
6
votes
2
answers
724
views
Has the following kind of (minimum degree $d$) random graph been studied?
The following random construction is simple enough that I am guessing it must have been studied. Fix $d \ge 3$, and let $n > d$. For each of the $n$ vertices, pick exactly $d$ other vertices to conne …
- 85.6k