Questions tagged [graph-theory]

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.

1,486 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
51 votes
0 answers
2k views

Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

A very specific case of Reed's Conjecture Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
Andrew D. King's user avatar
36 votes
0 answers
1k views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
Igor Pak's user avatar
  • 16.3k
32 votes
0 answers
3k views

Vertex coloring inherited from perfect matchings (motivated by quantum physics)

Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question. Added (25.12.2020): I made a youtube video to explain the question in detail. ...
Mario Krenn's user avatar
31 votes
0 answers
893 views

Is this representation of Go (game) irreducible?

This post is freely inspired by the basic rules of Go (game), usually played on a $19 \times 19$ grid graph. Consider the $\mathbb{Z}^2$ grid. We can assign to each vertex a state "black" ($b$), "...
Sebastien Palcoux's user avatar
29 votes
0 answers
977 views

Non-linear expanders?

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete ...
H A Helfgott's user avatar
  • 19.3k
26 votes
0 answers
648 views

Planar minor graphs

The theorem of Robertson-Seymour about graph minors says that there exists no infinite family of graphs such that none of them is a minor of another one. Apparently, it came as a generalization of ...
Pierre Dehornoy's user avatar
24 votes
0 answers
744 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, ...
Dustin G. Mixon's user avatar
23 votes
0 answers
482 views

Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$. Is ...
Wade Hann-Caruthers's user avatar
22 votes
0 answers
539 views

Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
Gordon Royle's user avatar
  • 12.3k
21 votes
0 answers
425 views

Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, ...
Lviv Scottish Book's user avatar
19 votes
0 answers
606 views

Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture. But for bigger Ramsey ...
Myshkin's user avatar
  • 17.4k
19 votes
0 answers
776 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 ...
Lee Mosher's user avatar
  • 15.3k
17 votes
0 answers
405 views

Is the Frog game solvable in the root of a full binary tree?

This is a cross-post from math.stackexchange.com$^{[1]}$, since the bounty there didn't lead to any new insights. For reference, The Frog game is the generalization of the Frog Jumping (see it on ...
Vepir's user avatar
  • 591
17 votes
0 answers
498 views

Maximum automorphism group for a 3-connected cubic graph

The following arose as a side issue in a project on graph reconstruction. Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a ...
Brendan McKay's user avatar
16 votes
0 answers
334 views

Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?

My question is Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must $G$ have the following substructures? i) a leafless spanning tree; ii) a spanning forest consisting ...
Agelos's user avatar
  • 1,844
16 votes
0 answers
242 views

Approximation of the effective resistance on Cayley graph

Let $\Gamma$ be a finitely generated group, and denote by $G$ the Cayley graph of $\Gamma$. Denote by $d_R$ the resistance distance metric on this graph. The resistance distance metric between the ...
Tomek Odrzygozdz's user avatar
16 votes
0 answers
1k views

Optimal monotone families for the discrete isoperimetric inequality

Background: the discrete isoperimetric inequality Start with a set $X=\{1,2,...,n\}$ of $n$ elements and the family $2^X$ of all subsets of $X$. For a real number $p$ between zero and one, we consider ...
Gil Kalai's user avatar
  • 24.2k
15 votes
0 answers
415 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
1k views

The threshold for a perfect matching in a random subgraph of a regular bipartite graph?

The following question seems very natural. It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the ...
Zur Luria's user avatar
  • 1,613
14 votes
0 answers
410 views

Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...
domotorp's user avatar
  • 18.3k
14 votes
0 answers
854 views

A Conjecture About Directed Graphs that are the Union of Two Trees

Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed spanning trees. Suppose that There no subset X of vertices so that there is precisely one directed edge from X to its ...
Gil Kalai's user avatar
  • 24.2k
14 votes
0 answers
513 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,...
Shiva Kintali's user avatar
14 votes
0 answers
449 views

How much must deleting a spanning tree reduce edge-connectivity?

Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What ...
Dave Pritchard's user avatar
14 votes
0 answers
893 views

Is every k-edge-connected graph also k-trail-ordered?

This is an old question of Aradhana Narula-Tam and Philip Lin that I think deserves wider circulation. It appeared in Discrete Math. 257 (2002), page 613, but not many people have looked at it and it ...
Timothy Chow's user avatar
  • 78.1k
13 votes
0 answers
698 views

Is there a weak strong regularity lemma?

A famous strengthening of Szemerédi's regularity lemma, due to Alon, Fischer, Krivelevich and Szegedy, allows one to partition a graph into a bounded number of pieces in such a way that not only are ...
gowers's user avatar
  • 28.7k
13 votes
0 answers
380 views

Are the zeros of Tutte polynomials dense in $\mathbb C^2$?

For the chromatic polynomials of graphs we have two nice theorems which describe the behavior of their zeros: Thomassen proved that the set of real zeros of all chromatic polynomials is the union of $\...
Gjergji Zaimi's user avatar
13 votes
0 answers
1k views

A new lower bound for the chromatic number of a graph?

Let $S_{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of a graph $G$. Let $S_{-}(G)$ denote the sum of the squares of the negative eigenvalues and $q$ the ...
Clive elphick's user avatar
13 votes
0 answers
733 views

$\epsilon$-nets with respect to the cut norm

The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
Aaron's user avatar
  • 794
13 votes
0 answers
1k views

Finding a chromatic polynomial by polynomial fitting

I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph ...
Douglas S. Stones's user avatar
12 votes
0 answers
253 views

Computing the number of ways to delete vertices sequentially without disconnecting a graph

Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph. ...
Dylan Thurston's user avatar
12 votes
0 answers
234 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 $...
Mare's user avatar
  • 25.8k
12 votes
0 answers
12k views

A New York Times tiles-based graph theory question

The New York Times has a daily puzzle named Tiles that works as follows. Start with $m$ squares (in the official version, this is 30, in a 6x5 grid), and a set of $p>4$ possible patterns (typically ...
David Pepper's user avatar
12 votes
0 answers
206 views

Does there exist 2-planar graph with chromatic number 8 or 9 or 10

A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...
Xin Zhang's user avatar
  • 1,130
12 votes
0 answers
316 views

Is there an algorithm to compute a Belyi map for the Riemann surface?

Let $y^2=x^5-x-1$ be an affine model of a projective complex curve, is there an algorithm to compute the Belyi map (preferably of small degree), i.e., map to the projective line ramified only at $\{0,...
Gregory Eritsyan's user avatar
12 votes
0 answers
327 views

The number of labeled pairs of edge disjoint trees and related questions

I wonder what is known on the following: 1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices? 2) (harder, it seems) What ...
Gil Kalai's user avatar
  • 24.2k
12 votes
0 answers
276 views

Is there a Rado category?

The Rado graph appears to have a nice universality property (it contains all finite and all countably infinite graphs as induced subgraphs) and homogeinety property (any isomorphism between finite/...
Qfwfq's user avatar
  • 22.7k
12 votes
0 answers
448 views

Colouring a graph whose edge set is a special union of cliques

I am trying to show that a certain family of graphs can always be properly coloured with at most $6$ colours (where "properly coloured" means that each vertex gets a colour and no edge has both ends ...
Gordon Royle's user avatar
  • 12.3k
12 votes
1 answer
2k views

Hobbled rook tour – Hamiltonian cycle on square grid

Consider a square grid of even side length ($2n \times 2n$). It is easy to see that there must exist a Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balanced if the number ...
John's user avatar
  • 121
12 votes
0 answers
1k views

Shortest path in Cayley graphs

The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...
user22070's user avatar
  • 121
12 votes
0 answers
894 views

Hamiltonian cycles and fundamental groups

I'm interested in the interplay between the Hamiltonian cycles of graphs and the compact surfaces they embed in. I was doing some reading on the Lovász conjecture for Cayley graphs, I started noticing ...
Gjergji Zaimi's user avatar
12 votes
0 answers
349 views

Matroids with prescribed independent sets

Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
ilyaraz's user avatar
  • 1,771
11 votes
0 answers
392 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 $...
Zach Hunter's user avatar
  • 3,393
11 votes
0 answers
527 views

How to determine the sign for the sum over all simple paths in the graph

$\DeclareMathOperator\perm{perm}\DeclareMathOperator\len{len}$Let $A$ be the adjacency matrix of a tree $T$ for some ordering $v_1,...,v_n$ of the vertices, and let $D=xI-A$ its characteristic ...
CHUAKS's user avatar
  • 785
11 votes
0 answers
272 views

Does every finite poset have a rigid endomorphism?

Crossposted on Mathematics. In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...
Pierre-Yves Gaillard's user avatar
11 votes
0 answers
225 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 ...
JonCC's user avatar
  • 211
11 votes
0 answers
226 views

Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...
domotorp's user avatar
  • 18.3k
11 votes
0 answers
303 views

How many n/2-cycles can a cubic graph have

Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have? A random cubic graph has $\Theta((4/3)^n/...
Brendan McKay's user avatar
10 votes
0 answers
183 views

Number of triangle-free graphs with prescribed number of edges

This question is posted from StackExchange since it received no answer there. Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
abacaba's user avatar
  • 344
10 votes
0 answers
737 views

Example of sequence of graphs which satisfy the Riemann hypothesis or the prime number theorem?

Let us look at the sequence of bipartite graphs $G_n = (V_n, E_n)$ where $V_n = A_n \cup B_n$ defined in this quesiton: Why is this bipartite graph a partial cube, if it is? . The shortest path ...
mathoverflowUser's user avatar
10 votes
0 answers
607 views

A rainbow perfect matching in an edge-colored graph with spanning color classes

This question is a sequel of my last question and is eventually motivated by recent advances in quantum physics. Given an even number $n\ge 6$ and a positive integer $k<n$, Claim from the linked ...
Alex Ravsky's user avatar
  • 4,102

1
2 3 4 5
30