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 questions only
not deleted
user 382
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.
16
votes
9
answers
3k
views
What is the Tutte polynomial encoding?
Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about …
- 35.5k
14
votes
3
answers
1k
views
Is there a matrix whose permanent counts 3-colorings?
Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean:
Kirchhoff's theorem says that if you tak …
- 2,821
16
votes
4
answers
2k
views
Checking if two graphs have the same universal cover
It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere.
You can define a notion of "covering graph" in graph theory, …
- 6,734
47
votes
4
answers
10k
views
Why are planar graphs so exceptional?
As compared to classes of graphs embeddable in other surfaces.
Some ways in which they're exceptional:
Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, mos …
CommunityBot
- 1
25
votes
5
answers
5k
views
Complete graph invariants?
Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a …
4
votes
8
answers
1k
views
Ways to "regularize" a graph
Are there any canonical methods, in graph theory, to produce a regular graph from a non-regular one? What I'm after is a construction which is as "categorically nice" as possible; for instance, to mak …
- 23k
13
votes
1
answer
1k
views
Combinatorial proof that large-girth graphs are sparse?
Theorem. Fix $\epsilon > 0$; for sufficiently large n, any graph with n vertices and $\epsilon \binom{n}{2}$ edges contains many (nondegenerate) cycles of length 4.
The proof is simple; put an in …
- 18.6k
9
votes
2
answers
1k
views
Is there a free digraph associated to a graph?
A little bit of background: A graph G is, of course, a set of vertices V(G) and a multiset of edges, which are unordered pairs of (not necessarily distinct) vertices. We say that two vertices v_1, v_2 …
- 25.2k
5
votes
2
answers
322
views
Smooth immersion(?) of graphs into the plane
Sorry if the terminology's wrong, I don't know differential topology. Also, this is more of a brain-teaser than a bona fide research question, but it's hopefully a "real mathematician"-level brain-tea …
- 14k