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
8 votes
0 answers
733 views

Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3? I know it is NP-complete for the ...
Florent Foucaud's user avatar
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 ...
Tony Huynh's user avatar
  • 31.5k
8 votes
0 answers
1k views

Simplicial Representations of (Hyper)Graph Complexes

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, ...
Gwyn Whieldon's user avatar
7 votes
0 answers
223 views

Chip firing on hypergraphs

A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...
Noah Schweber's user avatar
7 votes
0 answers
191 views

longest path transversals

In a connected graph any two longest paths intersect at a common vertex. It is open whether any three longest paths in a connected graph intersect at a common vertex. For a connected graph $G$, let ...
David Wood's user avatar
  • 1,243
7 votes
0 answers
149 views

Why is the crossing number of Tutte 12-cage 170?

From the Wikipedia entry on Tutte 12-cage , it is stated that the crossing number of Tutte 12-cage is 170, but the cited references do not seem to provide sufficient explanation for this. Exoo, G. &...
L.C. Zhang's user avatar
  • 1,605
7 votes
0 answers
162 views

Ring of invariants for graph automorphism

$\DeclareMathOperator\Aut{Aut}$Let $G$ be a finite simple graph with nodes numbered $1$ to $n$. Attach variables $x_1, ..., x_n$ to nodes. The graph automorphism group $\Aut G$ acts on nodes by ...
Rybin Dmitry's user avatar
7 votes
0 answers
295 views

"Meritocratic" pyramid schemes

There have been a couple of times in my life when people from multi-level marketing organizations attempted to recruit me. I listened to what they had to say, and both times I did not get involved ...
Favst's user avatar
  • 1,985
7 votes
0 answers
194 views

Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs

Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
Michał Oszmaniec's user avatar
7 votes
0 answers
380 views

Has the Moore graph problem been solved?

A $d$-regular (simple finite) graph $G=(V,E)$ with diameter $k$ is a Moore graph if $$ |V| = 1 + d \sum_{i=0}^{k-1} (d-1)^i. $$ It is known from the Hoffman-Singleton theorem and results of Damerall ...
S. Dewar's user avatar
  • 266
7 votes
0 answers
93 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 ...
John Machacek's user avatar
7 votes
0 answers
149 views

Does there exist an arbitrarily large bipartite graph that is critical of dimension 4?

Here's a question in geometric graph theory that I recently kicked the tires on but was unable to resolve. For a finite, simple graph $G$, say that $G$ is of dimension $n$, and write $\dim(G) = n$, if ...
Matt N's user avatar
  • 71
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, ...
Mircea's user avatar
  • 2,031
7 votes
0 answers
101 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 ...
user148575's user avatar
7 votes
0 answers
176 views

Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?

Let $A$ be a $2n$-by-$2n$ matrix with entries in $\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$ has rank $\...
H A Helfgott's user avatar
  • 19.3k
7 votes
0 answers
265 views

Chromatic polynomial and the circle

In https://arxiv.org/pdf/1208.5781.pdf It is proved that there is spectral sequence converging to $H^*(M^G,R)$ with the E1 page given by the graph cohomology complex $C_A(G)$ where $A:=H^*(M,R)$. My ...
Matthew Levy's user avatar
7 votes
0 answers
84 views

Universal point sets for 1-plane graphs

It is a notorious open problem to find a smallest set of $N$ points that permit any $n$-vertex planar graph to be drawn in the plane without crossings, using only those $N$ points as vertices, and ...
Joseph O'Rourke's user avatar
7 votes
0 answers
120 views

Does the problem of recognizing 3DORG-graphs have polynomial complexity?

A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...
Lviv Scottish Book's user avatar
7 votes
0 answers
93 views

Combinatorial region-halfplane incidence structures

I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate. Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...
Mikhail Tikhomirov's user avatar
7 votes
0 answers
206 views

IH-moves on trivalent graphs, and a complex that might be known to low-dimensional topologists

Here is a combinatorial problem which is hard to Google but seems like it might have a solution well known to people who study finite type invariants etc. Let $G_{g,b}$ denote the set of finite ...
Dan Petersen's user avatar
  • 39.2k
7 votes
0 answers
258 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$ ...
Henry.L's user avatar
  • 7,951
7 votes
0 answers
247 views

Why does a polynomial with discriminant $d=-163$ appear in this sequence?

Fact 1: Given the eta quotient, $$x_d= e^{2\pi\rm{i}/48}\,\frac{\eta(\tau)}{\eta(2\tau)}$$ where $\tau=\frac{1+\sqrt{-d}}2$, then $x_d$ for $d=11,19,43,67,163$ are the roots of the simple cubics, $$...
Tito Piezas III's user avatar
7 votes
0 answers
223 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-...
Florent Foucaud's user avatar
7 votes
0 answers
346 views

Missing count in number of perfect matchings

Let $f(G)$ give number of perfect matchings of a graph $G$. Denote $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Denote collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$. ...
Turbo's user avatar
  • 13.7k
7 votes
0 answers
227 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 ...
Tom Copeland's user avatar
  • 9,937
7 votes
0 answers
117 views

Contradicting claims about complexity of directed path graphs isomorphism

Thesis and a paper give conflicting claims about the complexity of graph isomorphism for directed path graphs. Since this means GI is polynomial likely I am missing something or there is something ...
joro's user avatar
  • 24.2k
7 votes
0 answers
186 views

"Edge Density" of Infinite Planar Graphs

Given an infinite planar graph $G$, let's denote by $\{H_1,H_2,\dots,H_m\}$ all the labeled graphs on $n$ vertices that appear as subgraphs of $G$. Also let $$d_n=\frac{\sum_{i=1}^m \#E(H_i)}{nm}$$ ...
Gjergji Zaimi's user avatar
7 votes
0 answers
196 views

Determinantal formulae for Tutte polynomial

Let $G$ be a connected undirected graph. Then the number $ST(G)$ of spanning trees in $G$ equals the following specific value of the Tutte polynomial of $G$: $ST(G)=T_G(1,1)$. On the other hand, ...
Fedor Petrov's user avatar
7 votes
0 answers
358 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 ...
Alex Saad's user avatar
  • 663
7 votes
0 answers
334 views

Does this inequality always hold?

Denote the adjacency matrix of a given undirected graph by $g$. It is an $n$-by-$n$ symmetric Boolean matrix with elements on the diagonal to be zero ($n\geq 3$). Let $g_{12}=g_{21}=g_{13}=g_{31}=1$ ...
liuchun deng's user avatar
7 votes
0 answers
740 views

Does this graph property have a name?

I'm interested in a family of properties of connected simple graphs that comes up in percolation theory. Let $G$ be a simple connected graph. Now consider the set of subgraphs of $G$ that I will call ...
Veit Elser's user avatar
  • 1,045
7 votes
0 answers
542 views

Graphs with graphic imbalance sequences

Let $G$ be simple undirected graph and $e=uv\in E(G)$. The imbalance of the edge $e$ is the value $imb(e)=|d(u)-d(v)|$. Let $M_{G}$ denotes the imbalance sequence (or more correctly, multiset of ...
Sergiy Kozerenko's user avatar
7 votes
0 answers
179 views

How quickly can we test if a graph is distance-regular?

A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...
Brendan McKay's user avatar
7 votes
0 answers
472 views

Maximum fractional chromatic number of a 4-regular triangle-free graph (updated)

Let $G$ be a graph with maximum degree 4 and clique number 2. The fractional version of Reed's Conjecture tells us that $\chi_f(G) \leq 7/2$. But how high can $\chi_f(G)$ be? The Chvátal graph has ...
Andrew D. King's user avatar
7 votes
0 answers
340 views

How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such ...
Niel de Beaudrap's user avatar
7 votes
0 answers
302 views

When can the Cheeger constant be well-approximated by ``Hamming balls''?

Given a graph G, the Cheeger constant is defined by $$ \DeclareMathOperator{\Vol}{Vol} h_G := \min_{S \subseteq V, \Vol S \leq (\Vol G)/2} \frac{|\partial S|}{\Vol S}. $$ Here, $\Vol S$ is the sum of ...
Eric Tressler's user avatar
7 votes
0 answers
279 views

Is there an analog of Khovanov homology for edge deletion-contraction-extraction?

Motivated by Khovanov's categorification of the Jones polynomial, several authors have worked on the categorification of graph invariants. For the chromatic polynomial some references are: "A ...
Gjergji Zaimi's user avatar
7 votes
0 answers
385 views

Sequence of graphs with small $\lambda_1$ (the smallest nonzero eigenvalue of a regular finite graph)

The combinatorial laplacian on a finite graph $G$ can be defined as $ \Delta: \mathbb{C}^G \to \mathbb{C}^G$ sending the function $f:G \to \mathbb{C}$ to $(\Delta f)(v) = \sum_{v' \sim v} \big( f(v)-f(...
ARG's user avatar
  • 4,342
7 votes
0 answers
396 views

What is this subclass of $k$-colorable graphs called?

The following property emerged naturally when I was playing with certain generalizations of Kneser graphs. Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows. ...
Gejza Jenča's user avatar
6 votes
0 answers
87 views

The uniform odd and even subgraph of $\mathbb{Z}^2$

Given a (first finite and later infinite) graph $G =(V,E)$ the uniform even graph is the uniform probability measure on the set of spanning even subgraphs. That is subgraphs (V, E') with $E' \subset E$...
Frederik Ravn Klausen's user avatar
6 votes
0 answers
122 views

Do vertex-maximal paths in 4-connected graphs intersect?

Call a path in a (possibly infinite) graph vmax (for vertex-maximal) if there is no path that covers a containmentwise larger subset of vertices. For example, in any spider graph the union of any two ...
domotorp's user avatar
  • 18.3k
6 votes
0 answers
224 views

Reference to a definition of a graph homology

Let $G$ be a graph, and define $C_k$ to be the free abelian group on the homomorphisms from graphs $H$ such that $K_k$ is a minor of $H$ without needing to do any vertex deletions, only edge ...
Sean Longbrake's user avatar
6 votes
0 answers
132 views

Graph-theoretic quasi-crystals?

I have recently been interested in the following purely graph-theoretic notion that weakens the assumption of transitivity in a similar way to how quasi-crystals have "(possibly) aperiodic long-...
tmh's user avatar
  • 685
6 votes
0 answers
408 views

Example of graph with strange property

I've also posted this problem in Math Stack Exchange (here). Note: Whenever I mention a coloring of a graph I'm referring to a proper coloring over its vertices using the least amount of colors. ...
Alma Arjuna's user avatar
6 votes
0 answers
366 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. ...
Karo's user avatar
  • 247
6 votes
0 answers
242 views

Catalan numbers from matchings?

There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
Per Alexandersson's user avatar
6 votes
0 answers
62 views

Vertex cover in bipartite graphs with bounds on cost and size

Suppose we have a bipartite graph $G$ with non-negative integer vertex costs. We would like to find a vertex cover of cost at most $C$ and size (number of vertices) at most $S$, where $C$ and $S$ are ...
Edith Elkind's user avatar
6 votes
0 answers
134 views

Hamilton cycles in random graphs with just enough connectivity

What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
Dmytro Taranovsky's user avatar
6 votes
0 answers
213 views

Lindström-Gessel-Viennot from properties of the $Alt^k$ functor?

Let $A$ be the directed adjacency matrix of an acyclic directed graph, with variables as its nonzero entries (one for each edge). The $(a,b)$ entry of the matrix $(I-A)^{-1}$ is the sum over all paths ...
Allen Knutson's user avatar
6 votes
0 answers
183 views

Maximum number of Hamilton paths in a tournament on $n$ vertices

Recall that a tournament is a directed graph $T$ such that for every pair of distinct vertices $\{v,w\}$, exactly one of the ordered pairs $(v,w)$, $(w,v)$ is an arc of $T$. A tournament is strongly ...
Gordon Royle's user avatar
  • 12.3k

1 2
3
4 5
30