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.
2
votes
Generalizations of the four-color theorem
Closely related conjectures are the following: An acyclic colouring of a graph is a colouring of its vertices so that the subgraph spanned on union of every two colour classes is acyclic (a forest). G …
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
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
3
votes
Generalizations of the four-color theorem
Consider a finite family of non-overlapping circles. We can ask what is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors? By Koebe’s c …
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
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
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 …
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
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
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 …
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). …
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
3
votes
Accepted
For what classes of comparability graphs are their complements also comparability graphs?
One source I found over the Internet is Information System on Graph Classes and their Inclusions. There you can find a page devoted to comparability graphs, complements of comperability graphs (a.k.a …
- 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
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