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 39521
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.
5
votes
Accepted
Graph such that edge contraction increases chromatic number
Any bridgeless bipartite outerplanar graph has the properties you describe, since:
Contracting any edge will introduce an odd cycle;
Outerplanar graphs are a minor-closed family and are all 3-colour …
- 12.4k
9
votes
A labelling of the vertices of the Petersen graph with integers
It is possible to exploit the symmetries of the Petersen graph, together with the rearrangement inequality, to reduce the size of a brute-force search from $15!$ to $129729600$ (a $10080$-fold improve …
- 12.4k
-1
votes
Self-complementary graph on 4k + 1 vertices
As the graph is self-complementary, by definition there exists some isomorphism $f$ from the graph to its complement. Consider $f$ as a bijection from the vertex-set of the graph to itself (i.e. a per …
- 12.4k
1
vote
Maximum number of four cycles with no intersecting three vertex paths
EDIT: This answer pertains to a misinterpretation of the question before it was later clarified, so does not answer the question as currently stated:
Two distinct 4-cycles share a 3-vertex path if …
- 12.4k
6
votes
0
answers
151
views
Upper bound on size of obstruction set for wye-delta-wye reducible graphs
A graph is $Y \Delta Y$-reducible if it can be reduced to an empty graph by the following operations:
$Y \leftrightarrow\Delta$ transforms;
Replacing multiple edges with single edges (parallel reduc …
- 12.4k
7
votes
1
answer
2k
views
Complexity of graph isomorphism
Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time:
$$ \exp(O(\log^c n)) $$
where $n$ is the number of vertices.
What is the best bound we have for $c$? (The ca …
- 12.4k
4
votes
Accepted
Product of geodesic distances
Note that if a graph is vertex-transitive, then it is `symmetric' by symmetry and we can wlog assume $i = 1$. The skeleton of the truncated icosidodecahedron is a counter-example to your conjecture, s …
- 12.4k
3
votes
Accepted
Name for directed graphs with "balanced cycles"
Yes, these are known as graded graphs.
(This terminology is used in Bela Bollobas's Modern Graph Theory, inter alia.)
- 12.4k
10
votes
Accepted
Finding the largest number which cannot be the sum of the labels of the Petersen graph
I can prove that all sufficiently large integers are representable.
Firstly, observe that there is a unique way, up to isomorphism, to choose three edges $p, q, r$ of the Petersen graph such that the …
- 12.4k
5
votes
Accepted
Number of Hamiltonian cycles on 24-cell graph
The Held-Karp algorithm for TSP can be modified to count Hamiltonian cycles. The idea is to fix a starting vertex $v \in V$ and inductively count, for every vertex $w \neq v$ and subset $S \subseteq V …
- 12.4k
6
votes
Subgraph isomorphism problem on 2d triangular lattices.
There exists a polynomial-time reduction from the NP-complete partition problem (special case of the subset sum problem) to determining whether a finite graph is a subgraph of the triangular lattice. …
- 12.4k
5
votes
Accepted
A generously vertex transitive graph which is not Cayley?
Take the graph product $G = P \times \mathbb{Z}$ of the Petersen graph with the infinite path graph. This is clearly infinite, finite-degree, and generously vertex-transitive.
Then we have two distin …
- 12.4k
1
vote
Accepted
Which is the most time efficient algorithm for having a Tait Coloring (edge-3-coloring) of p...
There is a quadratic-time algorithm for 3-edge-colouring a planar cubic graph, as described in the accepted answer to:
https://cstheory.stackexchange.com/questions/2578/complexity-of-edge-coloring-in …
- 12.4k
4
votes
Accepted
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles inter...
Yes, we can. Consider the usual drawing of the Fano plane with 7 vertices, 6 lines, and a circle. Replace the circle with a line through two of the three vertices.
Now we have 7 lines with 6 triple i …
- 12.4k
18
votes
2
answers
697
views
Can all unit-distance graphs have their vertices at algebraic integers?
A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can nec …
- 12.4k