Skip to main content

All Questions

65 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
24 votes
0 answers
760 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
14 votes
0 answers
522 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
11 votes
0 answers
228 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
8 votes
0 answers
181 views

Self-avoiding walks on strips

A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once. ...
Florian Lehner's user avatar
8 votes
0 answers
149 views

Edge-colorings of plane graphs: do you know references where the following questions are studied?

Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...
Florent Foucaud's user avatar
8 votes
0 answers
2k 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$ ...
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
  • 32.1k
7 votes
0 answers
97 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
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,041
7 votes
0 answers
171 views

What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?

Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
Elle Najt's user avatar
  • 1,462
7 votes
0 answers
279 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
  • 8,071
7 votes
0 answers
229 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
  • 10.5k
6 votes
0 answers
373 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
  • 277
6 votes
0 answers
116 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 ...
Jim Tilley's user avatar
6 votes
0 answers
359 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
  • 661
5 votes
0 answers
141 views

If chromatic polynomials for two graphs agree, can I always find an edge such that the two deletion-contraction minors have same chromatic polynomial?

Suppose I have non-isomorphic graphs $G$ and $H$ (which have at least one edge), but such that their chromatic polynomials are the same. Can I then always find an edge $e$ in $G$ and $f$ in $H$ such ...
Per Alexandersson's user avatar
5 votes
0 answers
231 views

Schröder and graphical logic?

I was actually surprised by a comment by John Baez over at the n-Category Cafe about his surprise that Ernst Schröder, a mathematician of whom he had known through Schröder's work on mathematical ...
Tom Copeland's user avatar
  • 10.5k
5 votes
0 answers
102 views

An upper bound on the minimum number of vertices in a girth 5 graph of chromatic number $k$

Is there a known upper bound on the minimum number of vertices in a graph with girth 5 and chromatic number $k$? Could you also give references for this?
user7952's user avatar
4 votes
0 answers
89 views

How to measure the optimality of the induced order by a median order of a tournament on a big subset

Median orders are great tools for dealing with a-priori unknown orientations of edges in tournaments, because they provide us with local properties on oriented edge density. I've been wondering if ...
alosc's user avatar
  • 71
4 votes
0 answers
228 views

How many arrangements of $n$ points with $k$ edge lengths exist in $d$ dimensions?

[Asking on behalf of a high school mathematics course, but responses written at any level are welcome!] I was recently reading over a nice puzzle called the four points, two distances problem: ...
Benjamin Dickman's user avatar
4 votes
0 answers
282 views

Reference for results about planar graphs

A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the ...
David Roberson's user avatar
4 votes
0 answers
207 views

Have wiring diagrams been generalized to arbitrary digraphs?

A "combinatorial wiring diagram" is a way to define a permutation by a drawing of a particular planar digraph. For example, this wiring diagram corresponds to the permutation $(3412)$: In Coxeter ...
GMB's user avatar
  • 1,389
4 votes
0 answers
123 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, \...
Jairo Bochi's user avatar
  • 2,479
4 votes
0 answers
111 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 ...
John Machacek's user avatar
3 votes
0 answers
61 views

Is this bipartite equivalent of 1-walk-regular graphs known?

A graph $G$ is 1-walk-regular if for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$. for each edge $vw$ the number of ...
M. Winter's user avatar
  • 13.6k
3 votes
0 answers
144 views

Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$

This should be a fairly standard question but I can't really seem to find a reference. Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
Sanchayan Dutta's user avatar
3 votes
0 answers
346 views

Terminology for transforming a directed acyclic graph into a tree

I am looking for the term of converting a directed acyclic graph (DAG) into a tree by traversing its topologically ordered nodes and copying the subtrees of the nodes with in-degree $> 1$. Such a ...
Dudi Frid's user avatar
  • 265
3 votes
0 answers
55 views

Efficiently drawing graph of maximum degree $3$ with at most $o(n^2)$ crossings

Let $G$ be simple finite graph of order $n$ and maximum degree $3$. Can we efficiently draw $G$ with at most $o(n^2)$ crossings? "Efficiently" means in time polynomial in $n$ or at worst $\exp{o(n^2)...
joro's user avatar
  • 25.4k
3 votes
0 answers
342 views

Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
Or Meir's user avatar
  • 419
2 votes
0 answers
65 views

Structure Theory for Tree Decompositions

I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer. Is is known when $G$ admits the following type of ...
Timothy_G's user avatar
2 votes
0 answers
165 views

Has Mac Lane's article "When can a graph be mapped on a torus?" been published anywhere?

I came across the following abstract of an article: Mac Lane, S., When can a graph be mapped on a torus?, Bull. Amer. Math. Soc. 42(9), 629 (1936). Abstract #341. MR1563375, JFM 62.0694.07. Q. Does ...
The Amplitwist's user avatar
2 votes
0 answers
86 views

Optimal paths in set-weighted graphs

Let $G = (V,E)$ be an $n$-vertex graph, let $R$ be a finite set (to be specific, let us assume that $R = [n]$), and let $W : V \rightarrow 2^R$. Let us call the pair $(G, W)$ a set-weighted graph. Now ...
Victor's user avatar
  • 655
2 votes
0 answers
124 views

Graphs which are built from complete graphs : Reference request

Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$. We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...
GA316's user avatar
  • 1,269
2 votes
0 answers
140 views

Lower bound for the chromatic number in terms of minimum feedback vertex set

Let $MFVS(G)$ denote the size of minimum feedback vertex set of $G$. We believe we proved $\chi(G) \ge (|G| - MFVS(\overline{G}))/2$ and this bound is sharp. Is this known or trivial result? This ...
joro's user avatar
  • 25.4k
2 votes
0 answers
30 views

Graph vertex label dynamics, statistical model reference request

I am modeling some type of social interaction, and came up with the following natural question. Let $K_n$ be the complete graph on $n$ vertices, with some initial edge labeling in some alphabet $A$. ...
Per Alexandersson's user avatar
2 votes
0 answers
50 views

An equation involving fractional covering number of hypergraphs

Let $\mathcal{H}=(S,\mathcal{X})$ be a hypergraph, where $S = \{ s_1, \ldots, s_n \}$, and $\mathcal{X} = \{ X_1, \ldots, X_m \}$. The dual hypergraph $\mathcal{H}^*$ of $\mathcal{H}$ is the ...
Victor's user avatar
  • 655
2 votes
0 answers
78 views

Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
George Octavian Rabanca's user avatar
2 votes
0 answers
116 views

Isomorphic subcategories of directed graphs and presets

For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...
Salvo Tringali's user avatar
2 votes
0 answers
216 views

Polyhedral embeddings of large face-width where all faces have the same length

Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length? By polyhedral embedding I mean an embedding of the graph on a ...
valle's user avatar
  • 884
2 votes
0 answers
642 views

Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of rectangular ...
Grzegorz Jaśkiewicz's user avatar
1 vote
1 answer
177 views

Spectral characterization of complete or complete bipartite graphs

The Lemma 6 in this paper mention the following spectral characterization of complete or complete bipartite graphs: Let $G$ be a connected graph with $\ge 2$ vertices. Then $\lambda_2=...=\lambda_{n-...
YuiTo Cheng's user avatar
1 vote
0 answers
74 views

Keller's cubing conjecture but with arbitrary cubes of side $1$

These days I have been reading about Keller's cube tyling conjecture, which asks if in any covering of $\mathbb{R}^n$ by translates of $[0,1]^n$ with disjoint interiors there are two cubes sharing one ...
Saúl RM's user avatar
  • 10.6k
1 vote
0 answers
381 views

Counting number of spanning trees of the complete bipartite with given vertex-degrees

For given $n_1,n_2 \in \mathbb{N}$ let $K_{n_1,n_2}$ be the complete bipartite graph. I have seen a few sources proving that the number of spanning trees $t(K_{n_1,n_2})$ is given by $n_1^{n_2-1} n_2^{...
Ben Deitmar's user avatar
  • 1,295
1 vote
0 answers
152 views

Is this graph theory paper in German translated into English?

I recently read such a paper and want to understand the proof idea of ​​this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
Licheng Zhang's user avatar
1 vote
0 answers
35 views

Term or reference for a set of integer edge weights to guarantee distinct weighted degrees

I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...
subset's user avatar
  • 11
1 vote
0 answers
134 views

Counting unions of unlabelled connected graphs

My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...
Bogdan's user avatar
  • 183
1 vote
0 answers
121 views

Cheeger constant of truncated hypercube

Look at the $d$-dimensional hypercube and truncate it. This means one replaces each vertex by a cycle (of length $d$) in such a way the the new graph is 3-regular. Question 1: What is the asymptotic ...
ARG's user avatar
  • 4,432
1 vote
0 answers
81 views

Matchings in infinite, not necessarily bipartite, graphs

Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs. Is there a similar generalization of Tutte's theorem on ...
Dominic van der Zypen's user avatar
1 vote
0 answers
29 views

Reference request for blocking sets in graphs

Let $G = (V,E)$ be a DAG and $S$ be a subset of $V$. I will call $S$ $k$-blocking if on every path of length $k~$ there is at least one node from $S$. This parameter sounds reasonable enough, so I ...
ivmihajlin's user avatar
1 vote
0 answers
151 views

Asymptotic estimation of numbers of unlabeled graphs whose degrees of vertices are bounded

It is known(Enumeration of graphs with a given and bounded degree sequence) that there is no a closed form formula for number of (labeled) graphs with bound on degree of vertices. Thus what I want to ...
Henry.L's user avatar
  • 8,071