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.
2
votes
Accepted
Do triple-linked graphs exist?
Yes.
Theorem 1.
For every $k$ there exists $N=N(k)$ such that in every embedding of the complete tripartite graph $K_{N,N,N}$ into $\mathbb{R}^3$ there are $k$ disjoint pairwise linked triangles; in p …
- 6,101
2
votes
Accepted
Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?
Already in the plane there are arrangements such that the longest path in their dual covers roughly at most $2/3$ of the regions, therefore they are not Hamiltonian. The reason is that the dual graph …
- 6,101
4
votes
Adjacency matrix of tournament
The following two papers give the lower bound $n-1$ on the rank of $n\times n$ tournament matrices over fields of characteristic zero. Here a tournament matrix $M$ is a $\{0,1\}$-matrix, with zeros on …
- 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
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
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
1
vote
What kind of graph has more edges than its line graph?
Matchings: the line graph of a matching has no edges.
Paths: the line graph of every path of length $k\ge 1$ has $k-1$ edges.
Paths might be the only connected graphs with this property, which may be …
- 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
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
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
1
vote
Digraphs with exactly one Eulerian tour
Graphs obtained from a (directed) cycle by a repeated operation of attaching a (directed) cycle to a vertex of degree $2$ have unique Eulerian tour.
The sequence appears in OEIS: http://oeis.org/A1026 …
- 6,101
3
votes
Edge coloring graphs is in P?
Holyer proved that the edge-coloring (chromatic index) of a graph is an NP-complete problem, even for cubic graphs: https://epubs.siam.org/doi/abs/10.1137/0210055.
So if $P\neq NP$, the best approxim …
- 6,101
3
votes
Minimizing the number of segments in drawings of planar graphs
Recently, Durocher and Mondal improved the upper bound for plane triangulations to $7n/3$:
https://doi.org/10.1016/j.comgeo.2018.02.003
- 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
3
votes
Accepted
Bookthickness of covering space
The graph of the icosahedron is a 2-fold cover of $K_6$; this covering can be induced by the covering of the projective plane by the sphere. The graph of the icosahedron is planar and Hamiltonian, so …
- 6,101