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.
1
vote
Simple proof that these graphs are perfect
It might be possible to prove that such graphs are perfect without first observing that they are Berge and applying the SPG Theorem, but I suspect this would be hard. It has been noted that the prope …
- 7,857
3
votes
How to describe a tree? (depth, degree, balance, ... what else?)
One metric on trees that has received a lot of attention over the past ten years is the one introduced by Billera, Holmes, and Vogtmann in their paper, "Geometry of the space of phylogenetic trees." …
- 7,857
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
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
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 …
- 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 …
- 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{ …
- 7,857
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$ …
- 7,857
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 …
- 7,857
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 …
- 7,857
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 …
- 7,857
21
votes
11
answers
4k
views
What are some good examples of non-monotone graph properties?
It seems that many, if not almost all, of the properties studied in graph theory are monotone. (Property means it is invariant under permutation of vertices, and monotone means that the property is e …
- 7,857
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 …
- 7,857
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 …
- 7,857