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 1463
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.
4
votes
Proving that every graph is an induced subgraph of an r-regular graph
Here's a silly group-theoretic proof.
Fix a free group F of suitably large rank, and realise it as the fundamental group of a rose R. Label and orient G so that there is an immersion G->R. Then G c …
- 25.2k
5
votes
Accepted
Planar Cayley graphs/complexes for coxeter groups
Let $\Gamma$ be the Coxeter group in question. Order the $s_i$ so that if $m_{ij}\neq\infty$ then $|i-j|\leq 1$. Now let $P$ be a polygon with edges $e_i$ and angles $\pi/m_{i,i+1}$ between consecut …
- 25.2k
8
votes
Accepted
Finite vertex-transitive graphs that look like infinite vertex-transitive graphs
For Cayley graphs, you're basically asking about residually finite groups.
A group $G$ is called residually finite if, for every non-trivial $g$, there exists a finite quotient $f:G\to Q$ such that $ …
- 25.2k
11
votes
Why do we associate a graph to a ring?
Your question (2) seems to me a completely valid question. I'm not aware of any old questions solved by the graphs you mention in your question, and I'd be interested to hear of examples, especially f …
12
votes
Accepted
? A graph is four colorable if and only if it is planar.
A graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. As Hunter's comment points out, $K_{3,3}$ is bipartite, ie two-colourable.
- 25.2k
2
votes
Limit Group decomposition
The question seems to arise from taking the quoted informal sentence a bit too literally:
Hence, a limit group can be obtained from abelian and surface groups by a finite sequence of free product …
- 25.2k
13
votes
Applications of infinite graph theory
Bass--Serre theory translates the algebraic notion of a `splitting' of a group $G$ into an action of $G$ on a (usually infinite) tree. See Serre's classic Arbres, Amalgames, $SL_2$.
- 25.2k