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 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
1
answer
341
views
The number of chains of chordal graphs
Consider a saturated chain $G_0 \subset G_1 \subset \cdots \subset G_m$ of graphs on $n$ labelled vertices, where $G_i$ has $i$ edges, and $m = {{n}\choose {2}}$. Altogether there are $m!$ such chains …
- 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
25
votes
3
answers
2k
views
Some models for random graphs that I am curious about
G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This …
- 24.7k
14
votes
0
answers
857
views
A Conjecture About Directed Graphs that are the Union of Two Trees
Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed
spanning trees. Suppose that
There no subset X of vertices so that
there is precisely one directed edge
from X to its c …
- 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
7
votes
1
answer
346
views
Edge Colorings of Directed Graphs which Respect an Involution
Let G be a graph and let C be a set of coloring. Suppose that there is an involution $\phi$ from C to C. We can think about the element of C as the nonzero elements of some Abelian group and $\phi(x)= …
- 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