**7**

votes

**0**answers

249 views

### A maximum discrepancy hypergraph 2-colouring problem

This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now.
The setup is as follows. We have a vertex set partitioned in to sets $V_1,\...

**7**

votes

**0**answers

710 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 ...

**6**

votes

**0**answers

101 views

### On the use of Weisfeiler-Leman refinement in Babai's GI proof

This question is for those familiar with the methods behind Babai's recent proof that graph isomorphism can be decided in quasipolynomial time. I am a newcomer to the GI problem, so I apologize if my ...

**6**

votes

**0**answers

105 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 ...

**6**

votes

**0**answers

78 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 ...

**6**

votes

**0**answers

261 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**6**

votes

**0**answers

286 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 ...

**6**

votes

**0**answers

167 views

### Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements:
(H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$.
...

**6**

votes

**0**answers

124 views

### Subgraphs of planar trivalent graphs

Let's think about planar trivalent graphs. (Or you can dualize and think about triangulations if you prefer.) It's easy to come up with a list of 'planar trivalent graphs with boundary' such that at ...

**6**

votes

**0**answers

301 views

### the length of paths in a specific graph

Let $n$ be a positive integer and $K$ be the set of all the $2$-elements subsets of $\{1,2,...,n\}$,then $|K|= \binom{n}{2}$. Define $$S=\{P\subseteq K:\bigcup_{I\in P}I=\{1,2,...,n\}\}.$$
For any $P\...

**6**

votes

**0**answers

148 views

### Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...

**6**

votes

**0**answers

403 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 ...

**6**

votes

**0**answers

322 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 ...

**6**

votes

**0**answers

214 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 ...

**6**

votes

**0**answers

349 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.
...

**6**

votes

**0**answers

382 views

### A binary bipartite graph - reference request

Consider the bipartite graph whose partite sets are two disjoint copies of $\{0,1\}^n$, with an edge joining $u$ and $v$ if and only if there is no position in which both $u$ and $v$ have $1$; that is,...

**6**

votes

**0**answers

1k 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$...

**6**

votes

**0**answers

678 views

### inverse eigenvalue problem on graph laplacian

I am trying to construct a graph Laplacian matrix from a set of eigenvalue. I've read several papers about inverse eigenvalue problems but to be honest I didn't understand clearly. Could somebody ...

**6**

votes

**0**answers

791 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, ...

**5**

votes

**0**answers

120 views

### Complexity of graph isomorphism

Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time:
$$ \exp(O(\log^c n)) $$
where $n$ is the number of vertices.
What is the best bound we have for $c$? (The ...

**5**

votes

**0**answers

74 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 ...

**5**

votes

**0**answers

100 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}$$
...

**5**

votes

**0**answers

104 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**5**

votes

**0**answers

106 views

### Does squaring a directed random graph more than double its out-degree?

As far as I know, it is an unsolved question
whether or not this is true:
If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least
double that of its ...

**5**

votes

**0**answers

95 views

### Graphs with no homomorphism and no minor relation

What is an example of two simple, undirected graphs $G,H$ such that
there are no graph homomorphisms between $G, H$, and
$H$ is not a minor of $G$, and $G$ is not a minor of $H$
?
Definition of ...

**5**

votes

**0**answers

86 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, ...

**5**

votes

**0**answers

58 views

### Perfect matchings of a regular, uniform, partite hypergraph

This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...

**5**

votes

**0**answers

81 views

### Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.)
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...

**5**

votes

**0**answers

133 views

### A digraph related to permutations

A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence.
Consider the following ...

**5**

votes

**0**answers

211 views

### When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...

**5**

votes

**0**answers

111 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 ...

**5**

votes

**0**answers

123 views

### Independent domination number for grid graphs

Let $G_{n,m}$ be the $n \times m$ grid graph, i.e. $G= P_n \Box P_m$, and $T_{n,m}$ the $n\times m$ torus grid graph, i.e. $G= C_n \Box C_m$, where $P_n$ and $C_n$ indicate the path graph of length $n$...

**5**

votes

**0**answers

191 views

### (Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...

**5**

votes

**0**answers

103 views

### Mapping graphs to ordinals

Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...

**5**

votes

**0**answers

183 views

### Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then $$\...

**5**

votes

**0**answers

97 views

### Implementations of Tutte polynomial [reference request, of a kind]

This question is not a 100% fit for MO, but it is a serious question that can be viewed as a sort of reference request, and I think fits here more than elsewhere.
I have been asked to write a chapter ...

**5**

votes

**0**answers

130 views

### Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...

**5**

votes

**0**answers

179 views

### A linear optimization problem on a graph

Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...

**5**

votes

**0**answers

238 views

### Graphs with many positive eigenvalues of their distance matrix

Let $G$ be a simple connected graph $D(G)$ its distance matrix and $n_{+}(G), n_{-}(G)$ the number of positive and negative eigenvalues of $D(G)$ respectively.
We call a graph $G$ optimistic if $n_{+}...

**5**

votes

**0**answers

170 views

### Diameter of subset sum graph

We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$.
Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its ...

**5**

votes

**0**answers

102 views

### making a graph well-covered without changing its Shannon capacity

This strongly relates to an earlier question of mine.
Let $G$ be a graph, $\alpha(G)$ its independence number and $\Theta(G)$ its Shannon capacity.
Question: can one 'add new vertices' to $G$ such ...

**5**

votes

**0**answers

179 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 ...

**5**

votes

**0**answers

304 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(...

**5**

votes

**0**answers

273 views

### Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...

**5**

votes

**0**answers

407 views

### “sum over labelings” representations of graph polynomials

It seems that there's a general way to go from "recursive" definition of a graph polynomials to "subset expansion" formulas.
Furthermore, polynomials with subset expansion formulas often have a ...

**5**

votes

**0**answers

606 views

### Counting graphs whose vertex induced subgraphs are members of a fixed set

Let $C$ be the class of graphs of girth $g$ or more. $C$ can alternatively be characterized as: $G \in C$ iff each of $G$'s vertex induced subgraphs on less than $g$ nodes is a forest.
We can ...

**4**

votes

**0**answers

106 views

### Automorphisms of an infinite graph built from a finite motif

Suppose we have a lattice $L$ in $\mathbb{R}^n$ for which we choose some fundamental domain $D\subset \mathbb{R}^n$ homeomorphic to a closed ball. Translates of $D$ by distinct elements of $L$ ...

**4**

votes

**0**answers

92 views

### A color interpolation lemma

I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof.
Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \...

**4**

votes

**0**answers

72 views

### Existence a class of graphs with special property

In the following, suppose all graphs are simple and finite. For a given graph $G$, we denote its complement by $\overline{G}$. Let $*$ be a binary operation among graphs, such as Cartesian product, ...

**4**

votes

**0**answers

76 views

### A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...