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

8
votes
4answers
267 views

Diameter of random segment intersection graph?

I have an even number of points $n$ randomly distributed (uniformly) in a disk. Then the points are randomly connected to form $n/2$ segments, a perfect matching. Finally, I form the intersection ...
0
votes
0answers
74 views

Gromov-Hausdorff distance measure between minimum spanning trees

I am trying to compare minimum spanning trees through time. I have two questions: 1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
0
votes
0answers
55 views

Strongly minimal covering subsets of $\text{Ind}(G)$

Let $G=(V,E)$ be any undirected, simple graph. Let $\text{Ind}(G)$ be the set of independent subsets of $V(G)$. We say that $K\subseteq \text{Ind}(G)$ is a cover (by independent subsets) if $\bigcup K ...
5
votes
0answers
69 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, ...
4
votes
1answer
94 views

Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?

What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable? Thanks in advance.
0
votes
1answer
98 views

Graph automorphisms that preserve independent sets [closed]

Let $G=(V,E)$ be a graph and $\mathrm{Ind}(G)$ be the collection of its independent sets. We call a graph automorphism $f:V \to V$ of $G$ good if it is non-trivial and ...
0
votes
1answer
49 views

Graph with finite chromatic number but infinite total chromatic number

Is there a graph $G$ such that $\chi(G)$ is finite, but there is no total coloring with finitely many colours?
3
votes
1answer
150 views

Partitioning a binary tree into vertex-disjoint subtrees

Say we have a labeled, binary unrooted tree $T$, i.e. each node has either 1 or 3 neighbors. Denote by $L(T)$ the set of leaves (degree-one nodes) of $T$. For some $L \subseteq L(T)$, denote by ...
5
votes
1answer
230 views

Chromatic number of graph defined on the set of permutations

For $n\in\mathbb{N}$ let $S_n$ denote the set of permutations on the set $\{1,\ldots,n\}$. Set $$E_n = \big\{\{\pi_1, \pi_2\}: \pi_1,\pi_2\in S_n \land \exists k_1 < k_2 <\ldots <k_r\leq n: ...
3
votes
0answers
50 views

The Class of Strong Resolving Graphs of Hamiltonian Outerplanar Graphs

I'll start with a couple important definitions. I'm not sure how well-known any of them are. Firstly, if $G$ is a graph, and $u, v \in V(G)$, say that $u$ is maximally distant from $v$, denoted $u\ ...
4
votes
2answers
144 views

Can we find 3 disjoint directed Hamiltonian cycles in the cube?

Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions. Can we partition the edges of $D$ into $d$ ...
0
votes
0answers
89 views

When does the normalized graph Laplacian have eigenvalue 1?

Let $G= (V,E)$ be a finite, undirected and unweighted graph with $V = \{v_1,\ldots, v_n\}$. Denote by $d_i$ the degree of $v_i$, i.e. the number of vertices that are adjacent to $v_i$. Let $A$ be the ...
2
votes
1answer
201 views

Does the minor graph of graphs on $\mathbb{N}$ have an uncountable independent set?

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. We write $V(G) := V$. If $S, T$ are disjoint subsets of $V(G)$ we say that ...
3
votes
1answer
295 views

Uncountably many countable graphs with no homomorphism between them

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such ...
1
vote
0answers
56 views

Proper edge colorings with no bi-colored 5-paths

Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way. It is well ...
2
votes
1answer
136 views

Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?

Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$. But do we have any quantitative ...
4
votes
1answer
116 views

Infinite graphs with “similar” Hom-sets

Let $G,H$ be infinite simple undirected graphs with the property that for any graph $X$ we have $|\text{Hom}(X,G)| = |\text{Hom}(X,H)|$. Does this imply that $G$ is isomorphic to a subgraph of $H$, ...
1
vote
0answers
35 views

Find paths in a graph that any 2 vertices can be reached through N of them

Given a undirected weighted graph. I would like to find a finite set of paths (consecutive vertices and edges) each shorter than L any two vertices can be reached through at most N(in my case N=4) ...
2
votes
0answers
123 views

Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...
7
votes
1answer
118 views

Does the Tutte polynomial of iterated cone graphs detect isomorphism?

Let $T_G(x,y)$ denote the Tutte polynomial of a graph. Of course we may have $T_G(x,y) = T_H(x,y)$ for $G$ and $H$ non-isomorphic graphs. Now let $c(G)$ denote the cone graph of $G$, i.e., the graph ...
1
vote
1answer
62 views

Graph classes which are not perfect but the stability number = clique cover numer?

I have a result for graphs whose stability number=clique cover number, which naturally includes the perfect graphs, but I'm curious about if there are other known and well-definable graph classes ...
7
votes
2answers
148 views

Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic. Now it feels to me that this class of graphs is "too ...
0
votes
0answers
25 views

Cardinality of maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...
-2
votes
1answer
75 views

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

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 ...
0
votes
0answers
28 views

Minimality of maximal expansions of a hypergraph cover

This is a follow-up question to 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 ...
0
votes
1answer
28 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$ ...
5
votes
3answers
274 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}$. ...
0
votes
1answer
255 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 two distinct functions $f,g:\mathbb{N}\to\mathbb{N}$ form an edge if and only if they differ in exactly one input $n\in\mathbb{N}$. ...
9
votes
2answers
321 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$?
5
votes
0answers
46 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 ...
3
votes
1answer
136 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
303 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 ...
23
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
256 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
75 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
2answers
151 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
92 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 ...
1
vote
1answer
99 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
97 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 ...
0
votes
1answer
121 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
179 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
173 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 ...
2
votes
1answer
169 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
184 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.
2
votes
0answers
49 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
62 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
106 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 ...
5
votes
1answer
131 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 ...
11
votes
3answers
319 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 ...