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 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.
63
votes
19
answers
12k
views
Generalizations of the four-color theorem
The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four c …
- 4,713
16
votes
0
answers
1k
views
Optimal monotone families for the discrete isoperimetric inequality
Background: the discrete isoperimetric inequality
Start with a set $X=\{1,2,...,n\}$ of $n$ elements and the family $2^X$ of all subsets of $X$.
For a real number $p$ between zero and one, we consider …
- 63.9k
36
votes
21
answers
6k
views
Generalizations of Planar Graphs
This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; …
- 4,713
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 …
- 37.7k
9
votes
1
answer
588
views
Spanning $k$-trees
##k-trees
A $k$-tree is a graph defined as follows: (They were defined by Harary and Palmer.)
a) A complete graph with $k$ vertices is a $k$-tree.
b) A $k$-tree on $n$ vertices $T$ is obtained by a $ …
- 24.7k
12
votes
0
answers
328
views
The number of labeled pairs of edge disjoint trees and related questions
I wonder what is known on the following:
1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices?
2) (harder, it seems) What …
- 24.7k
13
votes
3
answers
2k
views
Models for graphs representing real-life networks
I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks).
I will be thankful for answers t …
- 1,644
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 …
CommunityBot
- 1
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)= …
- 85.6k
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
9
votes
3
answers
2k
views
Weighted Regular Graphs
The following graph theoretic notion appeared in an economics paper entitled: "Prize competition under limited comparability, by Michele Piccione and Ran Spiegler which studies models of economics wer …
- 17.9k