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 1028
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
3
answers
515
views
Finding maximum value of degree-3 homogeneous polynomials when variables sum to 1
I would like to be able to find maximum values of degree-3 homogeneous polynomials, when the variables are non-negative real numbers that sum to 1. For example,
For example, the maximum value of $xy^ …
- 726
4
votes
Bound on the number of unlabeled cographs on n vertices
A cograph on $n$ vertices can be created by starting with $n$ 1-vertex graphs and then going through a procedure of at each turn either (1) complementing a graph, or (2) replacing two of your graphs w …
- 726
5
votes
What are some good beginner graph theory texts?
Wilson (many editions) - great to read quickly to get an overview.
Bondy and Murty (2008) - very clear, lots of stuff. My favorite book.
Diestel (2005) - clinical treatment.
Bollobas (1998?) - lots …
21
votes
8
answers
8k
views
Why is edge-coloring less interesting than vertex-coloring?
I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate.
…
13
votes
2
answers
402
views
Regularizing graphs
Let $G$ be a simple graph (undirected, no loops or parallel edges), with maximum degree $\Delta(G)$. I would like to add edges to the graph to make it regular, without increasing the maximum degree.
…
- 726
3
votes
Hamilton cycle decompositions of the complete graph
In Two-factorizations of complete graphs it is stated that $K_9$ has 122 non-isomorphic Hamiltonian decompositions, and the corresponding number for $K_{11}$ is 3140 (EDIT: the actual figure is much m …
- 726
6
votes
What introductory book on Graph Theory would you recommend?
Robin Wilson's Introduction to Graph Theory is very easy to read - I read it over a weekend. I definitely recommend you give this a quick read before plunging into Bondy and Murty, Diestel or West.
4
votes
Accepted
Complexity of determining if two graphs have same cycle matroid?
The following paper seems to show that this problem is polynomial equivalent to graph isomorphism (see section 5):
http://arxiv.org/abs/0811.3859
- 726
2
votes
A name for a claw-graph with paths attached to it
In this paper such graphs are referred to as "spiders" and "subdivisions of stars":
http://doi.wiley.com/10.1002/jgt.20244
- 726
21
votes
Accepted
What is the Tutte polynomial encoding?
No-one so far has mentioned matroids. The Tutte polynomial encodes some of the information from the cycle matroid of the graph. Two graphs with the same cycle matroid (and number of vertices) have the …
- 726