All Questions
Tagged with reference-request graph-theory
161 questions with no upvoted or accepted answers
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
19
votes
0
answers
782
views
Reference request: Parallel processor theorem of William Thurston
Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
- 15.4k
15
votes
0
answers
455
views
Grothendieck dessins d'enfants - current surveys or text you can recommend?
I was recommended this forum to be the leading site for algebraic geometry, so I would like to ask you a question about Grothendieck dessins d´enfants. My background is in maps on surfaces (graph ...
14
votes
0
answers
522
views
Reconstruction conjecture and partial 2-trees
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature,...
- 281
13
votes
0
answers
237
views
A Dynkin type classification result in linear algebra
Let $G$ be a finite directed acyclic graph. The Cartan matrix $C_G=C$ of $G$ is defined as the matrix with rows and colums indexed by the vertices of $G$ and $c_{i,j}$ counts the number of paths from $...
- 26.5k
11
votes
0
answers
537
views
Outline of the unpublished proof of Erdős-Sós conjecture
In this post, it was mentioned that a long time ago, Ajtai, Kolmós, Simonovits, and Szemerédi announced a proof that for sufficiently large $k$, every $k$-vertex tree $T$ is a subgraph of every graph $...
- 3,499
11
votes
0
answers
228
views
Is there a term for this graph subset?
Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:
If $c:V(G)\rightarrow [k]$ is a vertex ...
- 211
10
votes
0
answers
328
views
Thurston on the Robertson-Seymour theorem
Danny Calegari recounts here that Bill Thurston "gave one talk explaining his idea of a new proof of (some version of) the Robertson-Seymour theorem" at MSRI in 1996-1997. I could not find it in the ...
- 940
8
votes
0
answers
245
views
Did these graphs pop up somewhere?
Please let me know if the following graphs popped up in some problems.
Each of these graphs is described by 5 integers $n_1\geqslant k_1$, $n_2\geqslant k_2$, $l\geqslant 0$.
We take two complete ...
- 45k
8
votes
0
answers
181
views
Self-avoiding walks on strips
A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once.
...
- 2,671
8
votes
0
answers
1k
views
$R(3,6) = 18$, especially proving that $R(3,6)>17$
I'm studying the Ramsey numbers, especially $R(3,6) = 18$
I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...
- 181
8
votes
0
answers
435
views
Is there an "Erlangen Program" for Graph Theory?
There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially ...
- 13.2k
8
votes
0
answers
149
views
Edge-colorings of plane graphs: do you know references where the following questions are studied?
Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...
- 537
8
votes
0
answers
866
views
Decomposition of graphs as symmetric differences of copies of $K_{a,b}$
I was wondering if the following decomposition of graphs has been studied, whether it has a name, and what the literature might be on it.
Given a labelled graph G, we decompose its edge-set as a ...
- 1,444
8
votes
0
answers
2k
views
What is the best lower bound for the domination number in regular graphs of girth 5?
The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):
Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ ...
- 161
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k
7
votes
0
answers
97
views
What is known about chromatic polynomial of hypergraph at $-1$
Let $H$ be a hypergraph and let $P_H$ denote its chromatic polynomial. I am interested in the best results interpreting $P_H(-1)$. I am interested both in the general case (which I think is hard) as ...
- 7,875
7
votes
0
answers
74
views
Graphs all of whose cuts are positive
Let $(V, E, w)$ a weighted graph, with vertices $V$, edges $E$, and signed weight $w:E\to \mathbb R$.
I am interested to know other popular properties that are known to imply, or are equivalent to, ...
- 2,041
7
votes
0
answers
102
views
Median spaces as retracts of hypercubes
It is known (See e.g. here, Theorem 2.1) that median graphs are retracts of hypercubes.
Question: Is it also known that median metric spaces are retract of some $l¹$ product of unit intervals?
By ...
- 887
7
votes
0
answers
171
views
What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?
Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
- 1,462
7
votes
0
answers
279
views
Relations between Betti numbers for clique complex
Given a clique complex $K$ constructed from a discrete set of vertices (i.e. its faces are isomorphic to the set of cliques in the 1-skeleton of $K$.), it seems that the Betti numbers $\beta_k$ ...
- 8,071
7
votes
0
answers
232
views
The smallest order of a 4-chromatic graph of given girth
Let $n_4(g)$ denote the smallest order of a $4$-chromatic graph with girth $g$. It is known that $n_4(4)=11$ [2] and $n_4(5)=21$ [1]. By a famous proof of Erdös, it is known that $n_4(g)$ is well-...
- 537
7
votes
0
answers
229
views
Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?
The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1.
Has anyone seen these trees?
The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...
- 10.5k
6
votes
0
answers
373
views
Circle numbers on edges of a graph
Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. ...
- 277
6
votes
0
answers
116
views
The properties of almost all directed graphs
A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar ...
- 3,871
6
votes
0
answers
477
views
The topos of a graph
If $G$ is, for example, a finite directed graph, one can attach to it a topos $T_G$ whose objects are "$G$-sheaves". A $G$-sheave $F$ is the data of:
For each verticies $x$ a set $F(x)$, for each ...
- 42.4k
6
votes
0
answers
138
views
Counting $K_4$ on two graphs sharing the same vertices
Let $f(G)$ denote the number of $K_4$ in a graph $G$ and $e(G)$ denote the number of edges of $G$.
Consider two simple graphs $G_1$ and $G_2$ having the same set $V$ of $n$ vertices and let $H_1(U)$ ...
- 3,153
6
votes
0
answers
116
views
Chromatic numbers for coloring-constrained graphs
I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...
- 91
6
votes
0
answers
359
views
Have topographs been studied before?
This is my first post on MO so I hope this question is suitable. I have quite a few definitions which I will need to state before my questions at the end of this post. Please let me know if anything ...
- 661
6
votes
0
answers
749
views
Tensor product of quivers
As a special case of a general construction I have constructed "accidentally" a tensor product of quivers aka directed multigraphs (aka directed graphs for category theorists). Probably this ...
- 63.1k
5
votes
0
answers
141
views
If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?
Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
- 15.8k
5
votes
0
answers
121
views
The Smith decomposition of the graph Laplacian and Locality
Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
- 51
5
votes
0
answers
231
views
Schröder and graphical logic?
I was actually surprised by a comment by John Baez over at the n-Category Cafe about his surprise that Ernst Schröder, a mathematician of whom he had known through Schröder's work on mathematical ...
- 10.5k
5
votes
0
answers
102
views
An upper bound on the minimum number of vertices in a girth 5 graph of chromatic number $k$
Is there a known upper bound on the minimum number of vertices in a graph with girth 5 and chromatic number $k$? Could you also give references for this?
- 51
5
votes
0
answers
169
views
In the literature on infinite graphs, are there results on "periodizable" graphs?
Let $G=(V,E)$ be a connected countably infinite $k$-regular simple graph (no loops or multiple edges). For $A$ a finite subset of $V$, let me denote by $G_A=(A,E_A)$ the induced subgraph with vertex ...
5
votes
0
answers
308
views
Distance on Markov-chains/graphs and discrete Ricci-flow
I am trying to know if there is a notion of "distance" or pseudo-metric between markov-chains or graphs.
For the purpose of the question, the graph is weighted, and can be considered as labelled, so ...
- 51
5
votes
0
answers
158
views
Does this geometric graph have a name?
Along some geometrical speculations, I came across a graph $\Gamma$ defined as follows:
Let $S$ be the set of vertices of a regular $n$-gon. Then the "vertices" of
$\Gamma$ are the nonempty subsets ...
- 101
5
votes
0
answers
136
views
What's the variance in the Six Degrees model?
Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search.
I interpret the punchline as saying that if I start ...
- 30.3k
4
votes
0
answers
185
views
Olympiad problem relevant to $(a,b)$-feasible pair
Recently, a mathematical olympiad problem is proposed as follows:
Let $G$ be a graph with $|V| = 100$ and $\delta(G) \geqslant 10$. Prove that there is an integer $0 \leqslant k \leqslant 5$, such ...
4
votes
0
answers
43
views
On the connection graphs-knots-tensors
You can interpret a featureless graph as product of featureless abstract tensors; the tensors are then automatically totally symmetric as "leg crossing" in the graph interpretation is the ...
- 4,829
4
votes
0
answers
89
views
How to measure the optimality of the induced order by a median order of a tournament on a big subset
Median orders are great tools for dealing with a-priori unknown orientations of edges in tournaments, because they provide us with local properties on oriented edge density.
I've been wondering if ...
- 71
4
votes
0
answers
157
views
Independent sets with few neighbours
[Posted this first at math stackexchange, but it probably fits better here.]
I am looking for references about the following problem.
Given a (connected) bipartite graph $G$, find an independent set $...
- 338
4
votes
0
answers
59
views
Graph-class defined by matrix-like vertex-operations
Let $m$ be a positive integer. We define a (directed) graph on $m(m-1)$ vertices
$$V = \bigl\{(i,j) \mid i \ne j,\, i,j\in\{1,\dots,m\}\bigr\}$$
and edges as follows:
$(i,j) \in V$ is adjacent (...
- 577
4
votes
0
answers
230
views
Is this case of Barnette's Conjecture known?
Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my ...
- 3,499
4
votes
0
answers
228
views
How many arrangements of $n$ points with $k$ edge lengths exist in $d$ dimensions?
[Asking on behalf of a high school mathematics course, but responses written at any level are welcome!]
I was recently reading over a nice puzzle called the four points, two distances problem:
...
- 7,831
4
votes
0
answers
282
views
Reference for results about planar graphs
A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the ...
- 2,339
4
votes
0
answers
108
views
Reference on generalization of plane graph duality between bonds and simple cycles
Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a ...
- 1,462
4
votes
0
answers
236
views
Groups inducing edge-colorings on graphs. Is this concept known?
Are the following concepts known in graph/group theory, and if Yes, what are they called and where to read about them? Because I do not know better, I gave them placeholder names for now.
1. ...
- 13.6k
4
votes
0
answers
207
views
Have wiring diagrams been generalized to arbitrary digraphs?
A "combinatorial wiring diagram" is a way to define a permutation by a drawing of a particular planar digraph. For example, this wiring diagram corresponds to the permutation $(3412)$:
In Coxeter ...
- 1,389
4
votes
0
answers
764
views
Counting loops in degree: 1 or 2?
Here's what seems to be an annoying technicality when dealing with loops in graphs.
In the literature on expander graphs (and surely not only), it seems to be the convention that a loop at vertex $v$ ...
- 997