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 108556
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.
27
votes
Accepted
Is every positive integer the permanent of some 0-1 matrix?
The answer to the question is yes. Given $k$, the 0-1 matrix given by
$1$ $1$ $\dotsc$ $1$ $0$ $0$ $\dotsc$ $0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$ $\dotsc$ $0$ $0$ $\dotsc$ $0$ $0$ $0$
$0$ $0$ $1$ $1$ $ …
- 6,051
16
votes
Does there exist a graph with maximum degree 8, chromatic number 8, clique number 6?
Relevant footnotes to Fedor Petrov's nice, helpful, and completely correct answer.
Fedor's answer seems essentially unimprovable both in brevity and completeness (it's all there).
I hadn't expected …
- 6,051
13
votes
Accepted
Concepts in topology successfully transferred to graph theory and combinatorics with non-tri...
The question asks for concepts, not applications, so in a sense the example given in the OP isn't one.
Here are five quick examples:
(0) One could argue that girth is a transferral of the concept …
10
votes
Accepted
Graph automorphism group
Here is a complete answer.
The answer to Q1 is 'no, because $A_w=\{1,2\}$ and $A_s=\{1\}$'.
The answer to Q2 is 'no, $A_w$ contains merely two, while $A_s$ contains merely one element.
The answer to …
- 6,051
9
votes
Hermann Weyl's work on combinatorial topology and Kirchhoff's current law in Spanish
This is a relevant comment on an answer given in this thread, which the comment boxes cannot conveniently accommodate.
The summary of the 'current' given after "These days" in an answer in this threa …
- 6,051
7
votes
Non-isomorphic graphs with bijective graph homomorphisms in both directions between them
Here are two partial answers:
EDIT: (the following is tentative; in light of Jeremy Rickards example, which is vertex-3-connected, and with which I cannot find anything wrong, something must be wron …
- 6,051
7
votes
Accepted
Does there exist a nonsingular graph for which the determinant of its adjacency matrix remai...
Proposition. The unique smallest graph w.r.t. number of edges of the requested kind is
. (This graph is isomorphic to graph no. 126 below).
It has $6$ vertices and $8$ edges.
The determinant o …
- 6,051
7
votes
Where on the internet I can find a database of graphs?
Discrete ZOO should also be mentioned here. As of 2 March 2018, it reports to host 212238 graphs.
6
votes
Number of non-equivalent graph embeddings
Ad 1. One notion of two embeddings being equivalent is "there exists an ambient isotopy carrying the image of one embedding onto the image of the other". Another, stronger, notion, more usual in the l …
- 6,051
6
votes
Accepted
Measurable maximal independent set in infinite graph of bounded degree
A relevant statement is Proposition 4.2. in
[KST1999] A. S. Kechris, S. Solecki, S. Todorcevic, Borel Chromatic Numbers. Advances in Mathematics 141, 1-44 (1999)
In short, the proposition shows that …
- 6,051
5
votes
Accepted
Graph algebras a la Lovasz
Question 1. is, strictly speaking, ungrammatical, and vague in most interpretations. If by graph algebra you mean algebraic graph theory,
then the question is hopelessly broad. If by question 1. you …
- 6,051
5
votes
Applications of Perfect Matching
like to learn more about its applications in other domains - specifically in the "real world" (by that I mean something relatively widely useful instead of confined to a very strict vertical like a …
- 6,051
5
votes
Neighborhood fingerprint of a graph
Answer. Arguably the simplest infinite set of counterexamples to "Does the converse hold?" are provided by the Möbius ladder's vis-à-vis the prism graphs. Any pair of such graphs (of equal orders) bea …
- 6,051
5
votes
Accepted
Has the Total Coloring Conjecture been proved for complete graphs?
Yes, of course.
It is known and published for decades that
$n$ odd $\quad\vdash_{n:\omega}\quad$ $\chi''(K^n) = n$,
and
$n$ even $\quad\vdash_{n:\omega}\quad$ $\rightarrow$ $\chi''(K^n) …
- 6,051
5
votes
Is there a "knot theory" for graphs?
It is somewhat surprising (to me) that what to me seems the simplest nontrivial example of theorems exactly fitting the question in the OP has not yet been mentioned in this thread: the embeddings of …
- 6,051