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 answers only
not deleted
user 440
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.
9
votes
Collection of conjectures and open problems in graph theory
I think the answers already given by Thomas Kalinowski are more comprehensive, but Douglas B. West maintains another collection of open problems in graph theory at http://www.math.illinois.edu/~dwest/ …
- 4,713
5
votes
Accepted
Planar layouts of bipartite graphs
Any planar graph can be drawn with curves for the edges and its vertices in any position in the plane.
But with straight line segment edges, it's not always possible, even for graphs in which every ve …
- 1,446
9
votes
Accepted
The flip graph of triangulations
Just to add a little to Joseph's nice answer, for part 1 of your question: although the problem of computing the flip distance in polynomial time is wide open for triangulations of convex polygons, it …
- 18.6k
9
votes
Is it possible to check a graph for acyclicity in $O(|V|)$ time?
The answer for directed acyclic graphs is no: in any standard adjacency-list based representation you have to look at $\Omega(m)$ of the edges; it is not enough to look at $O(n)$ vertices and edges, e …
- 105
4
votes
Accepted
Name of an inductively defined sequence of graphs
It's not quite the same question, but the graphs that can be obtained by repeating either of the two operations (add a disjoint vertex or a dominating vertex), not necessarily in strict alternation, a …
- 18.6k
10
votes
An introductory text on expanders
Elementary Number Theory, Group Theory and Ramanujan Graphs (Giuliana Davidoff, Peter Sarnak, and Alain Valette, 2003) is intended to make the construction of expander graphs accessible to advanced un …
- 18.6k
6
votes
Acyclic proper coloring of 2-degenerate graphs
It is not true.
Let $G$ be a graph consisting of an independent set $I=\{v_1,v_2,v_3,v_4\}$ (blue below) and 18 additional vertices $u_{i,j}$, $u'_{i,j}$, and $u''_{i,j}$ where $i\ne j$ and each of th …
- 18.6k
3
votes
Tree-width of graphs in which any two cycles touch
This is not a complete answer but it suggests that you have not made your statement strong enough: Your condition that all cycles touch means that the set of all cycles forms a bramble. By the charact …
- 18.6k
4
votes
How to generating all flats of the cycle matroid of a graph?
Give the edges of the graph distinct weights. Then the flats are in 1-1 correspondence with the minimal forests, where a forest is defined to be minimal if no other lower-weight forest spans the same …
- 18.6k
12
votes
Accepted
Proof of Bondy and Chvátal Theorem
Let $G=G_0, G_1, G_2$, etc. be a sequence of graphs where each $G_i$ is formed by performing a single closure step to $G_{i-1}$ — that is, add an edge $uv$ to $G_i$ when $u$ and $v$ together have at …
- 379
3
votes
Spatial dimension of a finite graph
If $s$ obeys $k_{n-1}<s$, where $k_n$ is the kissing number of $n$-dimensional Euclidean space, then the star $K_{1,s}$ has dimension at least $n$. For instance, $K_{1,7}$ has dimension 3.
(In most c …
- 18.6k
1
vote
Vertex cover number vs matching number
The value is 2. (This is the integrality gap of the LP relaxation of vertex cover. See Frankl–Rödl graph on Wikipedia for a graph for which the integrality gap of the SDP relaxation is still 2.)
- 18.6k
5
votes
Accepted
Is there a standard name for this type of multidigraph?
I haven't seen the multigraph version, but non-multi directed graphs with at most one outgoing neighbor per vertex have been called directed pseudoforests, and with exactly one outgoing neighbor they …
- 18.6k
5
votes
Crossing number of some Sphere of Influence Graphs and relation to their coloring number
In a Euclidean space of any dimension, for a system of balls no center of which is interior to another ball, each ball can only be touched by $O(1)$ larger balls. This is a special case of Lemma 3.6 o …
- 18.6k
7
votes
Is the nth-power-sum graph connected?
By going from $x$ to $a^n-x$ to $b^n-(a^n-x)$ we can, in two steps, add or subtract any difference of $n$th powers. In four steps, we can add or subtract any difference of differences (a second-order …
