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 1532
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.
34
votes
Accepted
Why are planar graphs so exceptional?
(I think that the question of why planar graphs are exceptional is important. It can be asked not only in the context of graphs embeddable on other surfaces. Let me edit and elaborate, also borrowing …
- 24.7k
32
votes
Accepted
What have simplicial complexes ever done for graph theory?
There are quite a few examples where simplicial complexes, more general complexes, and algebraic topology in general had important impact on graph theory. (Usually, the applications are indirect and b …
- 24.7k
26
votes
Accepted
Why is "P vs. NP" necessarily relevant?
The $P \ne NP$ problem is the best way we know to formulate the belief (which was expressed even before the problem was formally stated) that certain specific algorithmic problems (such as finding a H …
- 24.7k
18
votes
Can you determine whether a graph is the 1-skeleton of a polytope?
A few more remarks, On the bright side: To determine if a given graph is the graph of a d-polytope is decidable. Tarski's algorithm for real closed fields can be used.
In dimension 3 as Sam Nead menti …
- 24.7k
16
votes
Can one make Erdős's Ramsey lower bound explicit?
Finding explicit constructions for Ramsey graphs is a central problem in extremal combinatorics. Indeed, computational complexity gives a way to formalize this problem. Asking for a graph which can be …
- 24.7k
11
votes
Generalizations of the four-color theorem
Let me mention here Thompson's three questions:
Question 1: Suppose that $G$ is the graph of a simple $d$-polytope with $n$ vertices. Suppose also that $n$ is even (this is automatic if $d$ is odd). …
10
votes
What are the implications of the new quasi-polynomial time solution for the Graph Isomorphis...
(a) What is the computational complexity of GI, is an example of a major question that we genuinely did not know the answer to even on a heuristic or conjectural level. Even now, whether GI is in P is …
10
votes
Can we realize a graph as the skeleton of a polytope that has the same symmetries?
There is an example of Bokowski, Ewald and Kleinschmidt of a 4-polytope with a certain symmetry of the graph that cannot be realized geometrically. The combinatorial construction is due to Kleinschmi …
- 24.7k
9
votes
Accepted
Help on the following extremal problem?
If you devide your set of vertices into $k$ ($k \in \mathbb{Z}_{\geq 3}$) sets $V_1, V_2,\dots,V_k$ and take all edges from $V_i$ to $V_{i+1\ (mod\ k)}$, then you get $(n/k)^k$ holes of length $k$. Th …
- 24.7k
9
votes
Generalizations of Planar Graphs
One interesting generalization is to "small classes of graphs." A class of graphs is small if the number of isomorphism classes of such graphs with n vertices is (only) exp (O(n)). Forests, planar gra …
- 24.7k
8
votes
Algebraic proof of 4-colour theorem?
There is an algebraic method by Alon and Tarsi which allows in certain cases to prove that certain graphs are $k$-colorable (in fact, even $k$-choosable). A famous case where this method prevails is t …
- 24.7k
8
votes
Generalizations of the four-color theorem
There are also interesting weak forms of the 4CT where the challenge is of course to give a direct proof. An immediate consequence of the 4CT is that every planar graph has an independent set of size …
8
votes
Connectivity of the Erdős–Rényi random graph
this is not really an answer to your question but just a related matter. As you point out the expected number of trees in a random graph is 1 already when p=c/n and is very large when p=logn/n so the …
- 24.7k
7
votes
Accepted
Degree Sequences and Graph Enumeration
Regarding the question of enumerating degree sequences. Richard Stanley's paper: A zonotope associated with graphical degree sequences, in Applied Geometry and Discrete Combinatorics, DIMACS Series in …
- 24.7k
6
votes
Accepted
Is there an analogue of the Erdős–Gallai theorem for simplicial complexes?
Very little is known about the question (and even about the easier case of vertex degrees), and it contains as a special case some notoriously hard questions: For example the case that all $d_i$s are …
- 24.7k