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 24076
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.
45
votes
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on ap...
Assuming an unpublished Ramsey-type result by Robertson and Seymour about Kuratowski minors [FK18, Claim 5], which is now "folklore" in the graph-minor community,
an asymptotic variant of the crossing …
- 6,101
19
votes
Accepted
Do there exist sparse graphs with large crossing number?
Take the following graph: start with the complete graph $K_5$, and replace every edge by $n/10$ paths of length $2$. The resulting graph has $n+5$ vertices, $2n$ edges, and crossing number $n^2/100$.
…
- 6,101
17
votes
Accepted
Page-turning number of a graph
The page-turning number of a graph $G$ is also known as the bandwidth of $G$ (https://en.wikipedia.org/wiki/Graph_bandwidth).
The Wikipedia page also contains values of the bandwidth for some special …
- 6,101
15
votes
Always a planar-drawn cycle through $n$ points
Every shortest cycle through the $n$ points is noncrossing. This can be easily shown by contradiction: if two edges are crossing, they form the diagonals of a convex $4$-gon, and we can replace them b …
- 6,101
13
votes
Are infinite planar graphs still 4-colorable?
Regarding Q1:
The graph is a subgraph of the visibility graph of the integer lattice. Every sublattice $x+2\mathbb{Z} \times 2\mathbb{Z}$ is an independent set in the visibility graph, and the integer …
- 6,101
11
votes
Accepted
Is every graph an isomorphic factor of some complete graph?
Q1: yes, this is a theorem by Wilson; see the first paragraph here: https://arxiv.org/abs/1604.07282
Edit: perhaps the book Decomposition of graphs by J. Bosak might be helpful (the preview on google …
- 6,101
11
votes
Accepted
Computational (conjecture) choices for a path
Let $S=\Sigma v_i$. If $S=0$, sort the vectors according to their angle along the unit circle. Then the corresponding closed path traces the boundary of a convex polygon.
In fact, the vectors $v_i$ ca …
- 6,101
10
votes
Accepted
Spanning trees of plane graphs containing an edge of every face
A triangulation has a spanning tree with the required property if and only if its dual graph has a hamiltonian path (is traceable).
Zamfirescu constructed a 3-regular 3-connected planar non-traceable …
- 6,101
8
votes
Accepted
Coloring of a graph representing the power set
For $k\ge n+1$ there is a proper coloring of $G$ where each set in $\mathcal{P}$ is colored by its cardinality. Then no vertex $v$ has a neighbor with the same color.
- 6,101
7
votes
Is a simple graph the "sum" of a partial order and its dual?
Here is a counting argument showing that almost all $n$-graph matrices are counterexamples.
There are $2^{(1/2+o(1))\cdot n^2}$ graphs on $n$ vertices, but only $2^{(1/4+o(1))\cdot n^2}$ partial orde …
- 6,101
6
votes
Accepted
Find all 2-planar drawings of $K_6$ and $K_7$
The list of all good drawings of $K_6$ can be found in the doctoral thesis by Nabil H. Rafla: https://escholarship.mcgill.ca/concern/theses/x346d4920
On pages 164-165 the drawings are described by the …
- 6,101
5
votes
Accepted
Wait time to grid network disconnection with failing edges
This is an approximation of the answer. The main message is that, indeed, the probability of disconnection is dominated by isolated vertices.
I will assume that $\delta=1/m$, for some large positive …
- 6,101
5
votes
Accepted
Find all Non-isomorphic good drawings of $K_{3,3}$？
The list of nonisomorphic good drawings of $K_{m,n}$ with $2\le m,n \le 3$ appears in the following paper:
Heiko Harborth,
Parity of numbers of crossings for complete n-partite graphs,
Mathematica Slo …
- 6,101
5
votes
Reference request: monochromatic paths in edge-colored complete graphs
For the multi-color Ramsey numbers of even cycles, Luczak, Simonovits and Skokan proved that $R(C_k;c)\le ck+o(k)$ for fixed number $c$ of colors and $k\rightarrow \infty$.
For odd cycles, Bondy and …
- 6,101
5
votes
Accepted
Chromatic number and graph polynomial
$G=K_{3,3}$ is a counterexample: it has chromatic number $2$ but $\mathrm{rad}(P_G)=3$; there are monomials with all three exponents $1,2,3$.
My conjecture would be that $\mathrm{rad}(P_G)$ is equal …
- 6,101