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 37432
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.
3
votes
Accepted
A weak version of planarity
A graph drawn in the plane (with edges represented by curves that do not pass through vertices except for their endpoints) is called $k$-quasi-planar if there are is no set of $k$ pairwise intersectin …
- 1,169
10
votes
A conjecture on planar graphs
This is just an elaboration on Brendan McKay's beautiful answer, but too long for a comment. The crucial idea is to simplify the problem by generalising it, introducing a maximisation on the indices o …
- 1,169
2
votes
Accepted
A variant of tree or tree-cut decompositions
I mentioned your type of decomposition to my colleague Konstantinos and he pointed out that it had appeared in the literature under the name "strong tree-decomposition"! D. Seese introduced it in 1985 …
- 1,169
3
votes
1
answer
508
views
Menger's Theorem for planar triangulations
I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in …
- 1,169
1
vote
Accepted
Representing graphs of diameter $2$ with full intersection graphs
The answer is no.
Let $G$ be the four-cycle $abcd$. Suppose there was a ground-set $X$ and a full family of sets $A, B, C, D$ such that $A$ represents $a$, $B$ represents $b$, etc.
Since $ab \in E(G)$ …
- 1,169
4
votes
Accepted
Existence of a 2-labelled Hamiltonian Path decomposition of $K_{2n}$
I think I have a proof that such a labelling cannot exist if $n$ is even.
Suppose we have a labelling $\ell : V(K_m) \to \{ a, b \}$ and a decomposition of $K_{m}$ into a family $\mathcal{P}$ of Hami …
- 1,169
3
votes
Accepted
Tree-width of graphs in which any two cycles touch
I tried to prove the statement for a while and I think I managed to narrow it down to one particularly difficult case. In the end, it led me to a counter example, showing there are no such values $g$ …
- 1,169
7
votes
3
answers
387
views
Tree-width of graphs in which any two cycles touch
Let $G$ be a graph s.t. any two cycles $C_1, C_2 \subseteq G$ either have a common vertex or $G$ has an edge joining a vertex in $C_1$ to a vertex of $C_2$. Equivalently: for every cycle $C$ the graph …
- 1,169
4
votes
0
answers
381
views
Induced minors and induced topological minors
Question: For which graphs $H$ is the following true?
Every graph that contains $H$ as an induced minor also contains $H$ as an induced topological minor.
Definitions:
Let $G$ and $H$ be graphs.
$H$ …
- 1,169
6
votes
Accepted
Equalizing Geometric means of Graph Cycles
I am not 100% sure I am not misusing the Perron-Frobenius Theorem, but I think that it justifies all the assumptions I am going to make in the following. The final construction itself is very simple.
…
- 1,169
10
votes
Accepted
Do planar graphs have an acyclic two-coloring?
G. Chartrand, H.V. Kronk, C.E. Wall showed in "The point-arboricity of a graph" (Israel J. Math., 6 (1968), pp. 169–175) that the vertex-set of any planar graph can be partitioned into three induced f …
- 1,169
9
votes
0
answers
498
views
A separation property of graphs of bounded tree-width
The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ no …
- 1,169
11
votes
3
answers
408
views
Two disjoint trees
Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which cov …
- 1,169