## New answers tagged graph-theory

0

It is not true. Let $G$ and $H$ be graphs, and let $p_{max}$ be maximal pseudo-coloring of the graph $H$. Show that the map $p((x,y))=p_{max}(y)$ is pseudo-coloring of graph $G\times H$. Fix some $\{u,v\}\in E(G)$. For arbitrary distinct colors $a,b$ there exist $\{k,l\}\in E(H)$ such that $p_{max}(k)=a$ and $p_{max}(l)=b$. Then the edge $\{(u,k),(v,l)\}$ ...

1

Simple random walk (and non-backtracking walk) on random regular graphs exhibit the cutoff phenomenon [1]. The extension to graphs with degree sequences came later; see [2] for nonbacktracking walks and [3] for simple random walk where backtrackings cause additional difficulties.
In another direction, component structure at criticality was described in a ...

8

Perhaps I can contribute to the history part the question, since I was quite close to the Institut Fourier at that time and was very interested in their work (I am a physicist). Grenoble now has several different research groups doing graph theory (like G-SCOP, Institut Fourier, GIPSA-lab, LIG) but I think L'Institut Fourier was the early one for graph ...

0

Here is my self-answer to (c), based on my self-answer to (b).
For any $f:V\to \mathbb{C}$ with $|f|_2^2=1$ and $|\langle f,\Delta f\rangle|\geq \alpha>0$, we obtain, proceeding as in my self-answer to (b), that there is an interval of the form $$I = \{(2m-1)M + 1, (2m-1) M +2, \dotsc, (2m-1) M + 2 C M\}\cap [1,N]$$
such that $\left|\langle f|_I,\Delta f|...

0

Let me show how to do (b), in a more general context than I set out in (b).
Let $f:V\to \mathbb{C}$ with $|f|_2=1$ and $|\langle f, \Delta f\rangle|\geq \alpha>0$.
Consider a partition of $V$ inducing an equivalence relation $\sim$. Define the linear operator $\Delta_\sim$ on functions $v:V\to \mathbb{C}$ by $$(\Delta_\sim v)(n) = v(n) - \frac{1}{d} \...

6

I can recommend Topics in Chromatic Graph Theory (Encyclopedia of Mathematics and its Applications) with editors Lowell W. Beineke and Robin J. Wilson. It is from 2015, and if you are interested in chromatic topological graph theory topics, there are three relevant chapters for you:
Chapter 1: Colouring graphs on surfaces, chapter 4: Hadwiger's conjecture, ...

9

A great and current reference is "Algorithms for embedded graphs" from Éric C. de Verdière, it is a 66 page synthesis of his course notes from 2017 (find here: http://monge.univ-mlv.fr/~colinde/cours/all-algo-embedded-graphs.pdf). Covers topological graph theory plus related algorithms e.g. to minimize edge length of embedded graphs.
See this quote ...

6

I would like to add one important aspect: it was known that $\mu(G)$ and $\sigma(G)$ can deviate by a large amount for larger values $k$. Now we have the proof of the improved (sharper) bound $\mu(G)\leq\sigma(G)$, but even though this is an improvement, Kaluza and Tancer also showed that a large gap exists already for small values of $k$: They showed there ...

5

This is an extended comment rather than an actual answer.
I think that any answer to your questions 1 and 2 is likely to be rather involved since the properties you ask are sensitive to small local changes in the graph. To illustrate what I mean, consider the following two graphs:
$G_1$ has vertices $u_n, v_n$ for $n \in \mathbb Z$, and edges $u_nu_{n+1}$ ...

8

Kaluza and Tancer have actually proved $\mu(G)\leq\sigma(G)$ in 2019: See their proof in the preprint "Even maps, the Colin de Verdière number, and representations of
graphs" on arxiv. Here is the link https://arxiv.org/pdf/1907.05055.pdf
You are right, the invariant $\sigma(G)$ of Holst and Pendavingh does not seem to have an established name yet.

7

What you conjecture has been conjectured (more or less explicitly) a few times before. In the paper by Bonato and Mohar that you reference, it is dubbed the Andreae-Schroeder conjecture.
I recently proved that it is true, i.e. the cop-number of toroidal graphs is at most 3, see this ArXiv preprint. See also this preprint, where a general bound $c(G) \leq \...

3

I got here via this question and I thought it may be worth sharing the following uncountable family of locally finite examples:
Pick an arbitrary set $S \subseteq \mathbb Z$. The vertex set of the graph $G_S$ is $\mathbb Z \times \mathbb Z$. For the edge set take all "vertical" edges from $(m,n)$ to $(m,n+1)$, horizontal edges $(m,n)$ to $(m+1,n)$ ...

20

@user161819 I wanted to make a comment but it got too long, so putting it as an answer. But please take it just as a comment for later, once everything is finished:
If I understand your comment to my answer correctly, you are aiming to change your algorithm for the torus so it works with ${\rm cr}(G)$. I think the whole MO community is keeping their fingers ...

4

Greedy coloring works here to show $2p$-choosability, I believe, and the hypothesis that $p$ is prime doesn't appear to be necessary. Write the cliques as $A = \{a_1, \ldots, a_{p+1}\}$ and $B = \{b_1, \ldots, b_{p+1}\}$, taking the notation so that $a_i$ has exactly $i-1$ neighbors in $B$ and vice versa.
First color the edges in the bigraph between $A$ and $...

2

So directed graphs are not well-quasi-ordered by butterfly minors; see the intro of [BPP]. Furthermore, there are reasons to think that many of the FPT results for graph minors may not hold in the directed setting (ie [PW]).
Yet, perhaps surprisingly, it may still be possible to get a structure theorem for butterfly minors! There is an ongoing project to do ...

36

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 lemma, $\operatorname{cr}(G)\ge \Omega(e^3/n^2)$, is true even for the pair crossing number on a fixed surface, such as a torus.
With Radoslav Fulek [...

3

The answer is no.
Let $G$ be the Hoffman-Singleton graph (hence n=50, k=42). Let $C_k$ be the disjoint union of 5 $K_8$s and a $K_{10}-C$ ($K_{10}$ with a 10-cycle removed). Any proper induced subgraph of $C_k$ with maximum degree at least 4 will contain a $C_3$ or $C_4$, which $G$ does not contain.

6

In addition to Carlo Beenakker's answer that gives Hall via Sperner directly, I think you can also get it by applying Hall's Theorem for Hypergraphs as follows. Let $G$ be a bipartite graph with partite sets $X, Y$, and write $V(X) = \{x_1, \ldots, x_n\}$. For each $i$, define a $1$-uniform hypergraph $H_i$ with vertex set $N(x_i)$ and edge set $\{ \{y\} : y ...

13

Penny Haxell's 2011 paper On Forming Committees in the American Mathematical Monthly explicitly uses Sperner's lemma to prove Hall's theorem for bipartite graphs (see theorem 4.1 and 4.2).

135

$\DeclareMathOperator\cr{cr}\DeclareMathOperator\pcr{pcr}$For the pair crossing number $\pcr(G)$, the short answer is yes the crossing lemma holds for drawings on the sphere, but it is not known whether it also holds on the torus.
The best and most current reference for you could be the survey article from Schaefer, updated in February 2020: “The Graph ...

2

The notion of $\mathcal{C}_j(G)$ is natural in terms of hypergraphs where is has been studied. If you rephrase in terms of a hypergraphs, then $\mathcal{C}_j(G)$ becomes the independence complex of the hypergraph. These have been studied a lot in (combinatorial) commutative algebra.
An independent set in a hypergraph is any subset of vertices which does not ...

3

No, there cannot be 17 such numbers in arithmetic progression (and there cannot be 5 such numbers with the corresponding property for triples).
Suppose we have such an arithmetic progression of length $k$, say $x,x+d,\ldots,x+(k-1)d$. I claim that if a prime $p$ divides any two of them then either it divides all of them (which cannot be the case), or else $p&...

1

To add to my previous answer, a paper of Szabó and Tardos from 2006 ("Extremal problems for transversals in graphs with bounded degree") has a result related to the complex you defined in 2.

7

The Electronic Journal of Combinatorics has many Dynamic Surveys one of which is The Graph Crossing Number and its Variants: A Survey by Schaefer which first appeared in 2013 and has been updated as recently as Feb 14, 2020. From the bottom of page 40 onto page 41 you will find this conjecture for complete bipartite graphs discussed (with many references). ...

4

It is a fascinating conjecture. The following might be a good reference for you: In 1997, Richter & Thomassen showed that
$$\lim_{n\to\infty}cr(K_{n,n})\left(\begin{array}{c} n \\ 2 \end{array}\right)^{-2}$$
exists and is at most $1/4$. If the conjecture is true, the value of this limit is exactly $1/4$.
(R.B. Richter, C. Thomassen, "Relations ...

4

I think the following graph works for $k = 1$:
It clearly has crossing number at most $2$ and local crossing number $1$.
In any drawing with $2$ or fewer crossings, the green cycles cannot cross (the spokes from the red vertices would create at least one additional crossing). Once we have embedded the green cycles and the black matching edges between them, ...

3

If I understand notation correctly $e_{ij}$ is the edge $\{a_i, b_j\}$ in $G$. I'll let $w_{ij}$ be the weight $e_{ij}$. I'll give an example showing the alternative method can fail to detect a negative cycle in $N$. Consider
$$w_{11} = \epsilon$$
$$w_{12} = B$$
$$w_{13} = B$$
$$w_{21} = B$$
$$w_{22} = A$$
$$w_{23}= B - \epsilon$$
$$w_{31} = B + 3\epsilon$$
$...

6

A Markov chain on the symmetric group with this transition graph (but with directed edges and weights) was investigated by Lam and Williams. This has since received considerable attention, and has been connected to "TASEP on a ring" if you are looking for search words (it doesn't appear that the graph itself has a name in this context).
I should ...

7

I like a lot the book from Beineke & Wilson (editors) "Topics in Topological Graph Theory" from 2009 for that purpose. Take a look at the article "Open Problems" from Archdeacon in this book. It is just like 5 pages or so, but inspired me a lot. I think you could find it very useful.

5

If you are interested in tangles in the sense of Robertson and Seymour, this is just to provide some perspective on it. I am working on this for my Ph.D. project and I thought maybe it is considered helpful if I share this high-level, intuitive perspective here (it is not a detailed definition):
The best and shortest description, I think, is given in the ...

1

Assuming that you mean to precolour $k$ subdiagonals and have no further constraints on the precolouring, the answer to both of your questions is no.
For every $n$ there is a precolouring which cannot be extended: choose colours $1, \dots n/2$ in the first row and colours $n/2+1, \dots, n-1$ in the second row (and thus the second column). Then there is no ...

1

For the case $n=8$, with the precoloring you describe the completion you give is indeed unique. I checked by writing the corresponding boolean program and let a solver enumerate all solutions: there is only one.
For the case $n=10$, consider the pre-colored $K_{10}$
$$\left(\begin{array}{rrrrrrrrrr}
X & & & & & 1 & 8 & 4 &...

29

Seymour and Robertson have indeed said that, and in fact they wrote that in their 2003 article in which they published the graph structure theorem.
Here is the quote from Robertson and Seymour „Graph Minors. XVI. Excluding a non-planar graph“ (Journal of Combinatorial Theory, Series B, Vol. 89, Issue 1, Sept. 2003, pages 43–76, doi:10.1016/S0095-8956(03)...

5

In general, finding the number of perfect matchings is #P-complete. But using the Edmonds "blossom" algorithm, one can decide effectively if the number is zero or not. And it's also easy using the same algorithm to figure out if the number is exactly 1 (in principle we can try removing the edges one by one and check in each case whether there is ...

0

I do not think there is a standard name for this, but I may prefer to call it $p$-random chromatic number....

8

There are no such graphs when $n$ is odd, by the handshaking lemma.
Conversely, for all even $n \geq 224$, we claim such a graph exists.
In particular, given two planar 5-regular graphs $G$, $H$ each drawn on the surface of a sphere, we can define the 'connected sum' of the graphs as follows:
remove a small disk (containing one vertex) from the sphere on ...

8

There is a 3-connected 5-regular simple $n$-vertex planar graph if and only if $n=12$ or $n \ge 16$ is even. See Recursive generation of 5-regular graphs by Mahdieh Hasheminezhad, Brendan D. McKay, Tristan Reeves in WALCOM: Algorithms and Computation, eds. Das and Uehara, Lecture Notes in Computer Science, vol 5431, Springer 2009. The number of such graphs ...

0

The first question asked is the just the maximum leaf number of the graph. The problem of finding it is in general NP-Hard. For references, I think a good one is this, which is algorithmic. A recent paper is here. Note that the maximum leaf number is $n-d(G)$ where $d(G)$ is the connected domination number of the graph $G$.
By the way, your notation seems ...

11

Maybe this is another useful reference for you, now I found the link:
Ralucca Gera, Stephen Hedetniemi, Craig Larson, Teresa W. Haynes (editors) (2018): Graph Theory: Favorite Conjectures and Open Problems
It is actually two volumes, and obviously more recent than the other reference I mentioned. It covers graph theory as a whole and does not focus on ...

5

Regarding your first question, I think the comment of Henrik Rüping gives the best answer.
Regarding your second question, I am not sure about a geometric interpretation, but maybe the following perspective is a helpful starting point for your intuition: look at the center of the group.
Let's call your group $G$ and define its center $Z(G)$ by
$Z(G):=\{g\in ...

2

I think Timothy Chow's comment is right that there is no result about planar graphs with your lemma as an explicit corollary.
I believe the following 2007 research paper by Guido Helden might be of use to you: http://publications.rwth-aachen.de/record/62349/ It is about hamiltonicity of maximal planar graphs and planar triangulations, and starts with a very ...

3

We have an implementation in C, freely available, you just need to contact me.
Nick Wormald

5

Here's the reference page from a computational topology course I took a while back.

1

This is nothing but an ordinary Markov chain whose state space is the set of oriented edges of the graph with the transition probabilities determined by the configuration of two adjacent oriented edges (more precisely, whether the distance between the endpoints is 0, 1, or 2). What do you want to know about this chain?

2

Equation (1) from the above answer can also be viewed as the case in which $n=1$ for $w(n,l).$ This is simply because the number of closed walks of length $2l$ on a one-dimensional cube is always 1 regardless of $n$.

4

This is a kind of inclusion-exclusion related to the identity
$$
\sum_{k=1}^m (-1)^{k+1} \binom{2m-1}{2k-1}A(2k-1)=1 \quad\quad(1)
$$
for all $m=1,2,\ldots$.
For a route on the $n$-cube with first step being vertical we label other $2k-1$ vertical steps, take a weight $(-1)^{k+1}A(2k-1)$ for such a configuration and sum up. For given $k$, you may choose $2k-...

16

My recommendation, try Lando and Zvonkin (2004): Graphs on Surfaces and Their Applications.
I think it is a great book which applies graphs embedded on surfaces to solving problems from other fields of mathematics. The style is very refreshing, vivid, and lively, I would say. The style reminded me of Hatcher's chapter 0 in his Algebraic Topology text, and of ...

2

This is a non-3-connected 1-planar example...

3

For an answer, see discussion of the degree of the Sperner boundary labelling in the Musin (2014) article https://arxiv.org/pdf/1405.7513.pdf
If the pdf link does not work try https://arxiv.org/abs/1405.7513
Effectively, a valid Sperner boundary labelling is a piecewise linear automorphism on the boundary with odd degree.

3

Corollary (Graham). A rational number $p/q$ can be written as a sum of finitely many distinct reciprocals of integer squares iff $p/q \in [0,-1+\pi^2/6)~ \cup ~[1,\pi^2/6)$.
For the statement of the full theorem from which this follows, see On Finite Sums of Unit Fractions, with Graham as the sole author. Link.
This result is not very significant, but in ...

Top 50 recent answers are included

#### Related Tags

graph-theory × 4036co.combinatorics × 1652

graph-colorings × 399

reference-request × 355

algorithms × 256

pr.probability × 224

spectral-graph-theory × 197

gr.group-theory × 164

computational-complexity × 163

random-graphs × 151

linear-algebra × 137

discrete-geometry × 128

extremal-graph-theory × 124

mg.metric-geometry × 98

matching-theory × 87

set-theory × 84

algebraic-graph-theory × 79

matrices × 70

trees × 69

bipartite-graphs × 69

hypergraph × 67

combinatorial-optimization × 64

perfect-matchings × 63

infinite-combinatorics × 61

nt.number-theory × 58