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 questions 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.
12
votes
3
answers
779
views
Connectedness of random distance graph on integers
This is not my field, a friend needs the answer for the following question. Suppose we have a decreasing probability function, $p: N \rightarrow [0,1]$ such that $sum_n p(n) = \infty$. Take the graph …
- 19.1k
5
votes
1
answer
320
views
Do longest paths in 4-connected graphs intersect?
Is there for every $k$ a $k$-connected graph whose longest paths do not have a vertex in common?
This is known to be true for $k\le 3$, see
Ayesha Shabbir, Carol T. Zamfirescu., Tudor I. Zamfirescu: I …
- 19.1k
6
votes
0
answers
126
views
Do vertex-maximal paths in 4-connected graphs intersect?
Call a path in a (possibly infinite) graph vmax (for vertex-maximal) if there is no path that covers a containmentwise larger subset of vertices.
For example, in any spider graph the union of any two …
- 19.1k
1
vote
0
answers
131
views
What are constructions for induced $C_5$-free graphs?
During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, othe …
- 19.1k
8
votes
1
answer
309
views
How many uniquely colored degree two vertices in 3-coloring of subcubic graph?
Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph?
I'm interested in any similar results as wel …
- 19.1k
8
votes
0
answers
63
views
Color edges of graph w/r/t large induced subgraphs
Can we color the edges of any graph $G$ on $2m-1$ vertices with two colors such that any induced subgraph with at least $m$ edges is non-monochromatic?
If true, this would be sharp as shown by the st …
- 19.1k
8
votes
1
answer
673
views
Red-blue alternating Menger's theorem
Suppose we have a graph where every edge is colored red or blue. We say that a path is alternating if the red and blue edges alternate in it. Our goal is to find many edge/vertex-disjoint alternating …
- 19.1k
21
votes
1
answer
1k
views
Red-blue alternating paths
Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where $V_k=\{v_1,\ldots,v_k …
- 19.1k
10
votes
2
answers
576
views
Can we select a rainbow matching if each degree is 6 and each colorclass is a C_6?
Suppose that we have a 2d-regular graph whose edges are colored such that the edges of each color form a cycle of length 2d. (So if the graph has 2n vertices, then there are n colors.) Is it true that …
- 19.1k
31
votes
5
answers
2k
views
Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?
Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges?
I know that the answer is …
- 19.1k
1
vote
0
answers
106
views
Turán number of even cycles with diagonal
Let $C_{2k}'$ denote the graph that consists of the cycle on $2k$ vertices and one more edge, a chord connecting two opposite, i.e., distance $k$ vertices of the cycle.
What is known about the Turán …
- 19.1k
4
votes
2
answers
342
views
Can we find 3 disjoint directed Hamiltonian cycles in the cube?
Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.
Can we partition the edges of $D$ into $d$ dir …
- 19.1k
5
votes
0
answers
76
views
Consequences of Ramsey-numbers of hypergraphs
We know that the (2-color) Ramsey-numbers for $3$-uniform hypergraphs are between roughly $2^{n^2}$ and $2^{2^n}$, and the situation is similar to $k$-uniform hypergraphs for every $k\ge 3$. (A recent …
- 19.1k
2
votes
0
answers
112
views
What is the projective dual of a planar graph?
Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a geometr …
- 19.1k
10
votes
1
answer
401
views
Are there non-trivial graphs that uniquely embed to hypercubes?
The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place.
The weight of a sequence is the number of $1$'s i …
- 19.1k