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

learn more… | top users | synonyms

-1
votes
1answer
40 views

How does deletion-contraction affect chromatic number? Can it increase chromatic number?

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...
1
vote
0answers
13 views

Minimality of maximal expansions of a hypergraph cover

This is a follow-up question to Maximal expansions of strongly minimal covers of hypergraphs -- for definitions refer to that question. Does every strongly minimal cover have a maximal expansion that ...
2
votes
1answer
11 views

Maximal expansions of strongly minimal covers of hypergraphs

Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E = V$. Moreover we assume that every $e\in E$ is contained in some maximal member $e'\in E$ ...
6
votes
3answers
152 views

Borel coloring of a graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$

The following question was asked in a comment by Joel David Hamkins in Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. ...
2
votes
1answer
155 views

Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$

Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let $$E:=\big\{\{f,g\}: f, g \in V \land f\neq g\land \exists k\in \mathbb{N} \text{ }\forall n\in\mathbb{N}\setminus\{k\} (f(n) = ...
10
votes
1answer
221 views

Graph $G$ with $\omega(G) = 2$ but $\chi(G) \geq \aleph_0$

Given an infinite cardinal $\kappa$, is there a graph $G$ that has no clique consisting of more than 2 points, but $\chi(G) = \kappa$?
-2
votes
0answers
53 views

Directed Graph Equivalence Class

Consider the following conversion involving directed graphs. To convert from $\mathcal{G}$ to $\mathcal{G}^u$ (they have the same number of vertices): $V_i \rightarrow V_j$ in $\mathcal{G}^u$ iff ...
5
votes
0answers
37 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
0answers
28 views

How to do I do a one to many bipartite matching of two sets? [closed]

I have a set $C$ and another set $A$. Both the set have integers such that any element in $C$ is greater than every element in $A$. I need form a one to many matching between set $C$ and $A$ such that ...
5
votes
1answer
124 views

Regular epimorphisms in the category of simple undirected graphs

Let $\textbf{Grph}$ be the category whose objects are graphs $G = (V,E)$ such that $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We sometimes write $E(G)$ for ...
7
votes
1answer
256 views

Under $\neg CH$, have countable unions of rationally independent numbers inner measure zero?

In their 1943 paper On non-denumerable graphs, Erdos and Kakutani suggest as likely the following proposition. (EK*) Suppose CH fails and $\lbrace M_n : n \in \omega \rbrace$ is a countable family of ...
22
votes
1answer
1k views

Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...
5
votes
1answer
236 views

A claim from “Graph minors - a survey” by Robertson and Seymour

Can someone give me a proof sketch for this: Let $\mathscr{P}_n$ be the set of all graphs which do not contain a path on $n$ vertices as a subgraph. Define the type of a graph inductively as: the type ...
1
vote
1answer
1k views

Does this linear algebra construction based on a graph have a name, and where has it been studied?

In the paper Kochen-Specker set with seven contexts by Lisonek, Badziag, Portillo and Cabello, the following construction is used : Question : Have such constructions been used elsewhere, and if so ...
0
votes
1answer
54 views

Connectedness of the complements of the connected subsets

EDIT: My original foolish version was instantly destroyed by Dylan Thurston; it consisted of questions 1 & 2 below. Thus now only new question 0 remains to be answered. Let $\ X:=M^n\ $ be a ...
2
votes
1answer
106 views

Probability of relations in network

Imagine, i have a predicate $\text{friends}(x_1, x_2)$ and I know that $p(\text{friends}(x_1, x_2)) = p_2$. If I generate a world of $n$ people ($x_1$ to $x_n$), I expect there to be $\binom{n}{2}p_2$ ...
1
vote
0answers
80 views

Are back edges mandatory in Ford Fulkerson algorithm?

Consider the algorithm of Ford Fulkerson where, for each iteration, you add flow along a path equal to the maximum residual capacity along this path. Does it exist, for every network, a choice of ...
3
votes
1answer
77 views

Average degree of neighbors in a simple graph (-> Friendship paradox)

Given a simple, undirected graph $G=(V,E)$ and $v\in V$ we set $N(v) = \{w\in V:\{v,w\} \in E\}$ and $\text{deg}(v) = |N(v)|$. The average degree of the neighbors of a vertex $v$, or $\text{ad}(v)$, ...
1
vote
1answer
80 views

Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?

Feedback vertex set is a set of vertices whose removal leaves an acyclic graph. It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...
2
votes
1answer
104 views

Regular and extremal monomorphisms in the category of graphs

Let $\textbf{Grph}$ be the category whose objects are graphs $G = (V,E)$ such that $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We sometimes write $E(G)$ for ...
4
votes
2answers
165 views

Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is $$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} ...
1
vote
1answer
164 views

Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...
4
votes
1answer
152 views

Graph of graph homomorphisms

For (finite or infinite) undirected, simple graphs $G, H$, let $V_{\text{Hom}} = \{f:G\to H:f\text{ is a graph homomorphism}\}$, and $E_{\text{Hom}} =\big\{\{f,g\}\subseteq V_{\text{Hom}}: ...
3
votes
1answer
153 views

Seymour's second neighborhood conjecture

Does anyone out there know if Seymour's second neighborhood conjecture is still open? if not, I would appreciate any references.
1
vote
0answers
39 views

Decomposing a weakly chordal graph into disjoint union of co-chordal graphs

A graph G is said to be co-chordal if it is $\bar C_n$-free for any $n \ge 4$. It is weakly chordal if it is $C_n$ and $\bar C_n$ free for all $n\ge 5$. Assume that the induced matching number of $G$ ...
5
votes
0answers
60 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 ...
4
votes
1answer
86 views

Example to show pairwise crossing number is not equal to crossing number

A common point of two edges in a graph drawing that is not an incident vertex is called a crossing. The crossing number $cr(G)$ is defined to be the minimum number of crossings in any drawing of ...
4
votes
1answer
92 views

lower bound on A(k,4,floor(k/2))

A(k,4,r) is the independence number of the Johnson graph J(k,r). What is the best known asymptotic lower bound on A(k,4,floor(k/2)) ? I only obtained ...
7
votes
2answers
193 views

Models for graphs representing real-life networks

I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks). I will be thankful for answers ...
1
vote
1answer
72 views

Linear algebra formulation for colored node graph isomorphism

(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.) Some basic definitions for completeness: Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph ...
4
votes
0answers
121 views

Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path. A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...
1
vote
1answer
55 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
1
vote
0answers
59 views

Probabilistic proof for expander existence [closed]

I am new to probabilistic proofs and trying to understand them better. Apparently, a common probabilistic proof focuses on the existence of expanders (eg. vertex expanders). I've been using the search ...
20
votes
2answers
1k views

An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
1
vote
1answer
218 views

Limit Group decomposition

I would need a clarification about a statement in the article Limit groups and groups acting freely on $\mathbb{R}^n$-trees by Vincent Guirardel. First recall that a limit group is a finitely ...
3
votes
1answer
90 views

Create matrix containing values in [0,1] where sum of all diagonals and anti-diagonals is fixed

The problem I am facing sounds at first glance pretty simple. However, as very often, it seems more complicated than I first assumed: I want to calculate a matrix $P = (p_{j,k}) \in \mathbb{R}^{n ...
5
votes
0answers
99 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 ...
3
votes
0answers
99 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
2
votes
0answers
57 views

Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $ \lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...
1
vote
0answers
38 views

Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...
4
votes
2answers
167 views

How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have. For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...
7
votes
1answer
117 views

Is there a Degenerate Dependency Local Lemma?

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded. Here I ask whether another possible generalization (for which I could not yet ...
25
votes
0answers
578 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 = ...
3
votes
2answers
135 views

The Hadwiger number of $L(K_n)$

For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows: $V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b ...
1
vote
1answer
126 views

Implication between Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture?

The Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture can be stated in a very similar form: Erdös-Faber-Lovasz conjecture: for all finite simple undirected graphs $G=(V,E)$ we have $\chi(G)\leq ...
9
votes
3answers
677 views

Is every graph an edge-crossing graph?

Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...
4
votes
4answers
317 views

Request for examples of 4-regular, non-planar, girth at least 5 graphs

Edit: As David Eppstein points out (in his answer below) the assumption that the graph is non-planar is redundant. Thank you to everyone who answered/commented. I have a problem about geometric ...
2
votes
1answer
42 views

Adding vertex-disjoint edges to reduce the diameter

Let $G=(V,E)$ be a finited connected graph, $V\neq \emptyset$. Let $[V]^2 := \big\{ \{v,w\}: v, w \in V\text{ and } v\neq w\big\}$. Given $F\subseteq [V]^2$ we say that $F$ is a vertex-disjoint ...
2
votes
0answers
20 views

Is it true that centrality measures in SNA are indicative for most important vertices only?

I read about the limitations of centrality measures on Wikipedia. It says that centrality measures are good only for identifying top most important nodes in a social network. Their relative values can ...
2
votes
1answer
132 views

Is the number of vertices bounded for fixed max degree and fixed diameter?

Are there positive integers $\Delta, d$ such that the following statement is true? For every $n\in \mathbb{N}$ there is a graph $G = (V,E)$ such that $|V| = n$, $\Delta(G) \leq \Delta$ ...