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 955
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.
22
votes
When does a graph underlie the Hasse diagram of a poset?
This problem was proved to be NP-complete in
J. Nešetřil, V. Rödl, Complexity of diagrams, Order 3 (1987) 321–330, https://doi.org/10.1007/BF00340774,
but a mistake was discovered, and later correct …
- 19.1k
15
votes
Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary rela...
This is false as shown by the following digraph.
From $x$ there is an edge to $v_p$, from $v_p$ there is a cycle of length $p$ to itself, and from $v_p$ there are $p-1$ different paths to $y$, of leng …
- 19.1k
11
votes
Accepted
The number of relevant scales for a finite metric space
First here is an $O(n\log n)$ upper bound. Make a complete graph whose vertex set is $X$ and the weights on its edges are the distances, $d(x_i,x_j)$. Consider a minimum weight spanning tree $T$ in th …
- 19.1k
9
votes
Is every path with this property shorter than another path with the same endpoints?
A very natural special case is the following:
For any $v_i\in V_1$, there exists exactly one $v_j\in V_1\setminus \{v_i\}$ such that there is a $u\in V\setminus V_1$ such that $uv_i,uv_j\in E$.
This m …
- 19.1k
8
votes
Accepted
Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?
If you divide the vertex set into 3 parts, A, B and C, with respective sizes $an$, $bn$ and $cn$, and add all the edges except the ones connecting two vertices inside A and a vertex from A and C, then …
- 19.1k
8
votes
Accepted
Die-rolling Hamiltonian cycles
UPDATE: I played around and came up with a construction (chance of containing a mistake is high!), below it I leave my original answer for explanation.
$\begin{array}{ccccccccccccccccccccccccc}
3&-&2 …
- 19.1k
7
votes
Accepted
Embedding of planar graphs
Bends are necessary, we have studied this problem in this paper: http://arxiv.org/abs/1009.1315.
- 19.1k
6
votes
A question on representation of graphs
Here is a modest improvement on the upper bound that shows $d=O(n\log\log n)$.
The base of the construction is the following.
Order the vertices according to some permutation as $v_1,\ldots,v_n$.
Fix …
- 19.1k
6
votes
Accepted
What is the maximum of the ratio $\vartheta(G)/\alpha(G)$?
It is infinite, in fact much stronger versions are also true, see e.g., Theorem 1 here:
http://arxiv.org/abs/cs/0608021
(Shannon capacity is between $\alpha$ and $\vartheta$.)
- 19.1k
6
votes
Variant of Graph coloring
Update 2017.09.26: As I've just learnt from Tamas Kiraly, this notion is well-studied and has several names, such as k-way cut, k-terminal cut, multiway cut. For at least three colors, the problem bec …
- 19.1k
6
votes
Is every graph an incomparability graph?
No and they are called incomparability graphs: https://en.wikipedia.org/wiki/Comparability_graph
- 19.1k
6
votes
Accepted
Regularizing graphs
It is always enough to add k+2 more vertices where k denotes the maximum degree. This is sharp as shown by the graph which is a cycle of length 5 plus two independent edges.
The proof is the following …
- 19.1k
5
votes
Accepted
A conjecture about odd path and odd cycle
False. As we want a counterexample, we naturally start with the Petersen graph, P. Note that for any vertex v of P and non-adjacent edge uw of P there is a Hamiltonian path from v to w that does not u …
- 19.1k
5
votes
Non-unique 2-factorization of 2k-regular graphs
No and in fact your multigraph construction is the counterexample. Just replace each edge with an "almost 6-regular" graph, like $K_7$ minus one edge, uv, and connect u and v respectively to the endpo …
- 19.1k
5
votes
Edge-coloring of the complete graph without any rainbow paths
This is an open problem, see the intro of this paper for more details:
http://www.renyi.hu/~gyarfas/Cikkek/136_orthogonal.pdf
- 19.1k