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.

Filter by
Sorted by
Tagged with
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
11 answers
4k views

What are some good examples of non-monotone graph properties?

It seems that many, if not almost all, of the properties studied in graph theory are monotone. (Property means it is invariant under permutation of vertices, and monotone means that the property is ...
Matthew Kahle's user avatar
22 votes
4 answers
3k views

Brute force open problems in graph theory

Usually, a graph theoretic problem asks whether some class of graphs $C$ possesses a quality $P$. For example, $C$ is the class of all graphs and $P$ is the reconstructability property in Kelly-Ulam ...
22 votes
5 answers
4k views

Collection of conjectures and open problems in graph theory

Is there something similar to the Kourovka Notebook for graph theory (or anyway an organized, possibly commented, collection of conjectures and open problems)?
user avatar
22 votes
6 answers
5k views

The matrix tree theorem for weighted graphs

I am interested in the general form of the Kirchoff Matrix Tree Theorem for weighted graphs, and in particular what interesting weightings one can choose. Let $G = (V,E, \omega)$ be a weighted graph ...
bc919's user avatar
  • 323
22 votes
2 answers
879 views

Is every 1-million-connected graph rigid in 3D?

It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$: Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
Joseph O'Rourke's user avatar
22 votes
2 answers
8k views

Cubic graphs without a perfect matching and a vertex incident to three bridges

The example shown below (courtesy of David Eppstein) is a common example of a cubic graph that admits no perfect matching: (source: uci.edu) Are there other examples of cubic graphs that do not ...
Anthony Labarre's user avatar
22 votes
3 answers
1k views

Which paths in a graph are orthogonal to all cycles?

Start with some standard stuff. Suppose we have a directed graph $\Gamma$. I'll write $e : v \to w \,$ when $e$ is an edge going from the vertex $v$ to the vertex $w$. We get a vector space of 0-...
John Baez's user avatar
  • 21.3k
22 votes
2 answers
1k views

Graphs, K-theory and combinatorial balls: conjectures

The following conjectures from Kapranov and Saito's Hidden Stasheff polytopes in algebraic K-theory and in the space of Morse functions aren't as well-known as they aught to be, so I'd like to state ...
Romeo's user avatar
  • 2,714
22 votes
2 answers
2k views

Largest graphs of girth at least 6

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges. ...
Brendan McKay'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
10 answers
4k views

Why do we associate a graph to a ring? [closed]

I don't know if it is suitable for MathOverflow, if not please direct it to suitable sites. I don't understand the following: I find that there are many ways a graph is associated with an algebraic ...
21 votes
7 answers
1k views

Reference for topological graph theory (research / problem-oriented)

I would be interested in recommendations for topological graph theory texts. I think Gross and Yellen has a great chapter on topological graph theory, and I find Mohar and Thomassen's Graphs on ...
21 votes
3 answers
2k views

Obstructions for embedding a graph on a surface of genus g

Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings. Is the ...
Dr Shello's user avatar
  • 1,160
21 votes
8 answers
8k views

Why is edge-coloring less interesting than vertex-coloring?

I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate. ...
21 votes
2 answers
1k views

Why are the numbers counting "ever-closer" lattice paths so round?

Let $u(i,j)$ denote the number of lattice paths from the origin to a fixed terminal point $(i,j)$ subject only to the condition that each successive lattice point on the path is closer to $(i,j)$ than ...
David Callan's user avatar
  • 1,125
21 votes
4 answers
13k views

How many $p$-regular graphs with $n$ vertices are there?

Suppose that there are $n$ vertices, we want to construct a regular graph with degree $p$, which, of course, is less than $n$. My question is how many possible such graphs can we get?
Youzhou Zhou's user avatar
21 votes
4 answers
3k views

Can you determine whether a graph is the 1-skeleton of a polytope?

How do I test whether a given undirected graph is the 1-skeleton of a polytope? How can I tell the dimension of a given 1-skeleton?
Hans-Peter Stricker's user avatar
21 votes
3 answers
3k views

Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality? Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has $$ \int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \,...
Yufei Zhao's user avatar
21 votes
2 answers
3k views

Graphs with only disjoint perfect matchings

Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings). Examples: Cyclic graph $C_n$ with even ...
Mario Krenn's user avatar
21 votes
3 answers
1k views

Probability that random weights on $K_n$ satisfy triangle inequality

Given $K_n$, if a random real weight between $[0, 1]$ is chosen for every edge, what is the probability that the graph satisfies the triangle inequality? How about the discrete version, where the ...
aelguindy's user avatar
  • 343
21 votes
6 answers
3k views

"The" random tree

One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ ...
Ian Agol's user avatar
  • 66.8k
21 votes
2 answers
3k views

Is there a graph with 99 vertices in which every edge belong to a unique triangle and every nonedge to a unique quadrilateral?

99-Graph: Is there a graph with 99 vertices in which every edge (i.e. pair of joined vertices) belong to a unique triangle and every nonedge (pair of unjoined vertices) to a unique quadrilateral?
user avatar
21 votes
4 answers
1k views

A graph with few edges everywhere

Given a graph $G(V,E)$ whose edges are colored in two colors: red and blue. Suppose the following two conditions hold: for any $S\subseteq V$, there are at most $O(|S|)$ red edges in $G[S]$ for any $...
filipm's user avatar
  • 1,359
21 votes
2 answers
1k views

The chromatic number of the union of two graphs

Let $G_n$ be the graph on the set of all binary strings of length $n$ with two strings adjacent whenever they are Hamming distance $2$ away from each other, or one of them lies below another one; thus,...
Seva's user avatar
  • 22.8k
21 votes
2 answers
900 views

Seymour's second neighborhood conjecture for infinite graphs

Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only ...
Thomas Bloom's user avatar
  • 6,608
21 votes
3 answers
1k views

Why are Dynkin diagrams characterized by their eigenvalues?

The Dynkin diagrams An, Dn, E6, E7, E8 can be characterized among finite simple connected graphs by the property that their eigenvalues (that is, the eigenvalues of their adjacency matrices) all have ...
Qiaochu Yuan's user avatar
21 votes
5 answers
1k views

Spectral theory of graph Laplacian besides $\lambda_2$

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...
John D. Cook's user avatar
  • 5,147
21 votes
1 answer
1k views

A strange sum over bipartite graphs

While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
Brendan McKay's user avatar
21 votes
1 answer
764 views

Girth of the symmetric group

Let $n \in \mathbb N$ and $\{\sigma,\tau\} \subset {\rm Sym}(n)$ be a generating set. Question: What is the maximal possible girth (if one varies $\sigma, \tau$) of the associated Cayley graph? I ...
Andreas Thom's user avatar
  • 25.3k
21 votes
2 answers
4k views

Fast Fourier transform for graph Laplacian?

In the case of a regularly-sampled scalar-valued signal $f$ on the real line, we can construct a discrete linear operator $A$ such that $A(f)$ approximates $\partial^2 f / \partial x^2$. One way to ...
TerronaBell's user avatar
  • 3,039
21 votes
2 answers
459 views

Labeling binary trees so that adjacent vertices differ by a power of two

Let $T$ be a finite rooted binary tree (where "binary tree" means that each node has at most two children, possibly less) with $n$ nodes in total. Is there a labeling of the nodes of $T$ with the ...
Gro-Tsen's user avatar
  • 29.9k
21 votes
1 answer
1k views

Monomer-Dimer tatami tilings need better relationships with other math. Summary of results

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the tatami condition if no four tiles meet at any point. (Or you can think of it as the removal of a matching from ...
Alejandro Erickson's user avatar
21 votes
1 answer
1k views

Red-blue alternating paths

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where $V_k=\{v_1,\ldots,v_k\...
domotorp's user avatar
  • 18.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
20 votes
13 answers
4k views

Local-global approach to graph theory

This question is inspired from (i) Theorems like the "universal friend theorem": If every two vertices in a connected graph $G$ share a unique common neighbor, then there is a vertex connected to all ...
Gjergji Zaimi's user avatar
20 votes
5 answers
2k views

The middle eigenvalues of an undirected graph

Let $ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{2n} $ be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references ...
Tomaž Pisanski's user avatar
20 votes
6 answers
861 views

Hamiltonian paths where the vertices are integer partitions

I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n. Let the vertices of the graph G=G(n) denote all the p(n) ...
Burhan's user avatar
  • 323
20 votes
3 answers
968 views

Does the hypergraph of subgroups determine a group?

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
Dominic van der Zypen's user avatar
20 votes
2 answers
1k views

Erdős, Harary, Tutte's "dimension of graph": Progress in last 48 yrs?

I just ran across this delightful paper by an amazing triumvirate: Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20. (Cambridge link) ...
Joseph O'Rourke's user avatar
20 votes
4 answers
2k views

What algebraic structures are related to the McGee graph?

Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes. The ...
John Baez's user avatar
  • 21.3k
20 votes
1 answer
4k views

What have simplicial complexes ever done for graph theory?

(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...) Are there examples of results in "classical" [*] graph theory that have been achieved by using simplicial ...
Felix Goldberg's user avatar
20 votes
2 answers
1k views

Non-definability of graph 3-colorability in first-order logic

What is a proof that graph 3-colorability is not definable in first order logic? Where did it first appear?
Leo Marcus's user avatar
20 votes
3 answers
1k views

Can a 3-regular non-1-planar graph be constructed?

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing. I used nauty to generate all 3-regular graphs up to ...
L.C. Zhang's user avatar
  • 1,605
20 votes
3 answers
3k views

Proofs of parity results via the Handshaking lemma

I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency). Let me ...
20 votes
1 answer
1k views

A Ramsey avoidance game

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...
Daniel Soltész's user avatar
20 votes
1 answer
4k views

Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq: Gonthier, Georges. Formal proof—the four-color theorem. Notices Amer. ...
Nate Eldredge's user avatar
20 votes
2 answers
866 views

Is there an analogue of the Erdős–Gallai theorem for simplicial complexes?

The Erdős–Gallai theorem gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. In particular $d_1 \ge d_2 \ge \dots \ge d_n$ ...
Matthew Kahle's user avatar
19 votes
8 answers
6k views

Generating function in graph theory

I am looking for a simple illustration of generating functions in graph theory. So far, the matching polynomial seems to be the best. But I want something bit richer; at least a derivative should ...
Anton Petrunin's user avatar
19 votes
5 answers
7k views

What is the probability that two random walkers will meet?

It is a well known result that a random walk on a 2D lattice will return to the origin see Polya's random walk constant. Based on this, it is not a big stretch to conclude that the random walk will ...
Jeremiah Edwards's user avatar