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.
1
vote
Do degrees determine the chromatic number?
There is also a general principle one can apply: If you have any parameter $\alpha$ of graphs so that there is an efficient (polynomial-time) algorithm to compute $\alpha (G)$, then it is extremely i …
- 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
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 …
1
vote
What is known about the chromatic number for minimum-distance graphs in higher dimensions?
This is a very good question. Maybe I miss something but I don't know an example where the lower bound is not polynomial. There is an example of an infinite periodic configuration where the minimum de …
- 24.7k
3
votes
Accepted
Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?
It does follow from Euler's theorem that every graph of a 3-polytope has either a triangle face or a vertex of degree 3. To see this note that if every face has 4 or more edges then $4F \le 2E$ (doubl …
- 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
4
votes
Reasons for the importance of planarity and colorability?
I agree with the points of David Eppstein's answer on the important of planarity. I can add also my answer to a similar problem. We still need a good answer on why colorability is so important. As Tim …
3
votes
Accepted
Number of homomorphisms from graph $H$ to $G$ , bounds that have to do with fractional color...
You are referring to E. Friedgut and J. Kahn, On the number of copies of one hypergraph in another, Israel Journal of Mathematics 105 (1998), 251–256.
For graphs this result is the very first paper o …
- 24.7k
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
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
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
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). …
4
votes
Generalizations of the four-color theorem
Let $P$ be a $d$-dimensional polytope with $n$ vertices. For every $2$-dimensional face $F$ triangulate $F$ by non crossing diagonals. So if $F$ has $k$ sides you add $(k-3)$ edges. It is known that …
3
votes
Generalization of Hamiltonian cycles to "Hamiltonian spheres"
Amos Altshuler studied a related notion in his Ph. D. thesis and the paper "Altshuler, Amos Manifolds in stacked $4$-polytopes. J. Combinatorial Theory Ser. A 10 1971 198--239." In his version he allo …
- 24.7k
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