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.
2
votes
Chromatic tiling complexity and the chromatic number conjecture
It can be strict already for $d=2$. Let $T$ consist of five tiles: a square, and four very silly shapes that nevertheless can be put together such that they pairwise share a $1$-dimensional face (ther …
- 19.1k
2
votes
Accepted
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is highly unlikely that such a generalization would exist, because the 3-dimensional matching problem is NP-complete, while polynomial identity testing can be solved efficiently using randomized al …
- 19.1k
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 …
- 35.5k
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 …
- 1,446
3
votes
Regarding a specific Turán number of graphs
A graph of girth $g$ can have at most $O(n^{1+\frac1{\lfloor\frac{g-1}2\rfloor}})$ edges. This is known as the Moore bound, though now the only reference I could find online right now is this one: Dut …
- 12.9k
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
5
votes
Completing subcubic trees to cubic graphs
Yes. First make $T$ cubic in any way. In each step, while the graph has a cycle whose length is less than $g$, pick a shortest cycle $C$ and one edge $uv$ of it. There are at most $6\cdot 2^g$ vertice …
- 19.1k
2
votes
Accepted
Representation of $x$-non-monotone curves with one intersection each by $x$-monotone curves
This answer, as pointed out by Jan in the comment, is incorrect, as the definitions slightly differ. I leave it here as it contains useful pointers.
If I understood your definitions correctly, your $\ …
- 19.1k
1
vote
Strongly minimal covers for clique hypergraphs of graphs
I can prove the following weaker statement, which was not true in the other version:
Every hypergraph stemming from the cliques of a graph has a minimal cover, where I define a cover as minimal if the …
- 19.1k
1
vote
Accepted
Complexity of games with graph classes
No, it is not possible to go above PSPACE, because all positional games with an exponentially large game tree are in PSPACE; you can just check all the options. And the game when $A=B=\emptyset$ is in …
- 19.1k
5
votes
Ramsey-Turán density function is well defined
New Answer: It indeed follows from vertex-multiplication. If you replace each vertex with a stable set of size $k$, then $\alpha(G)/n$ will not change, while $n^r$ and the number of edges both grow by …
- 227
1
vote
A non-distinct system of representative edges
Are you aware of the literature on systems of disjoint representatives? It has the same definition as yours, except that $f(G_i)=f(G_j)$ is not allowed. Here is the classic paper of Aharoni and Haxell …
- 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
3
votes
Does every graph $G$ contain a triangle-free subgraph $H$ such that $H \cup e$ contains exac...
This is false. Here is how to construct a counterexample.
Suppose $abc$ is a triangle in $G$.
Also suppose that there are many (at least two) vertices in $G$ whose only neighbors are $a,b,c$.
A simple …
- 19.1k
4
votes
Accepted
Does a bounded branching/log depth dihotomy hold for rooted trees?
Call a tree on $x$ vertices low if its branch-depth is at most $\log x$.
We prove by induction that for every tree on $n$ vertices there are some numbers $a,b$ such that $n\le ab$ and the tree contai …
- 19.1k