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
vote
1answer
94 views

Eulerian graphs with prescribed number of edges

Under what conditions there exists an $n$-vertex eulerian graph with $m$ edges for $1\leq m\leq\frac{n(n-1)}{2}$?
8
votes
1answer
176 views

Expansion in strongly regular graphs

Have you seen the following statement proven anywhere? Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...
11
votes
1answer
285 views

Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?

This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route ...
1
vote
1answer
55 views

Duality and Euler paths in graphs

I'm computer scientist and in one of my researches I'm facing this question: if I have a planar graph that admits an Euler path (i.e. has 0 or 2 odd degree vertices, as Euler's theorem says), then his ...
9
votes
3answers
257 views

Labeling edges of an icosahedron with sum constraints

The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that: Three ...
1
vote
0answers
23 views

Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph. I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...
3
votes
1answer
102 views

Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. ...
0
votes
1answer
39 views

Number of $k$-walks containing a vertex in an unweighted multigraph

Let $G = (V,E,W)$ be a weighted graph, where each edge $e = (v_i,v_j)$ has weight $w_{ij} \in \mathbb Z^+ \cup \{0\}$. By replacing $e$ with $w_{ij}$ copies of unweighted multiedges, a weighted graph ...
2
votes
3answers
206 views

Making integer multisets graphic

Let $M=(X,f)$ be a multiset, where $X$ is the underlying set of elements and $f:X\rightarrow\mathbb{N}$ is the multiplicity function. For every $k\in\mathbb{N}$ put $k\cdot M:=(X,k\cdot f)$. It is ...
19
votes
0answers
307 views

Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
1
vote
2answers
72 views

Position likelihood in a 2D graph [closed]

I am looking for general principles or specific answers to this generic example. Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...
4
votes
0answers
71 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 ...
6
votes
2answers
263 views

extremal bipartite graph

I'm facing the following question: Given a bipartite graph $G = (L \cup R, E)$. Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$. What is a minimal possible number ...
4
votes
1answer
86 views

$k$-planar graphs and genus

Is there a simple function that connects $k$ in $k$-planar graphs and genus of such graphs? If there is no simple function is there any non-trivial upper and lower bound?
3
votes
0answers
78 views

Group Travel Salesman Problem

For the following Group Traveling Salesman problem, I'd like to know if there exists some poly-time approximation algorithm with constant approximation factor. Group TSP is defined as follows: Take a ...
7
votes
2answers
241 views

A Different 2-factor in a graph

We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891). My question is in ...
-1
votes
2answers
73 views

Is there a formula that determines the size of the leafage of a graph's spanning tree? [closed]

In general terms, all the spanning trees of a graph G have the same number of leaves. Is there any formula that allows us to know the number of leaves in terms of |V| and |E| for any spanning tree of ...
0
votes
2answers
106 views

Infinite k-connected planar graphs

By planar I mean there is no $K_{3,3}$ minor of $K_5$ minor. Also, I am only considering the $\mathbb{R}^2$ surface, not a torus not any other surfaces. I know that to construct such graph, For $k ...
2
votes
1answer
130 views

Does this version of Hadwiger's conjecture hold for graphs with infinite chromatic number?

Let $G = (V,E)$ be a finite, simple, undirected graph. Hadwiger's conjecture states that (Hadw): $K_{\chi(G)}$ is a minor of $G$. It turns out that for finite graphs, (Hadw) is equivalent to the ...
2
votes
0answers
51 views

The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...
-1
votes
1answer
107 views

Graph such that edge contraction increases chromatic number

Let $G=(V,E)$ be a simple, undirected graph with the following properties: Contracting any edge increases the chromatic number by $1$; For each minor $M$ of $G$ we have $\chi(M) \leq \chi(G) + 1$. ...
1
vote
1answer
109 views

Simple Graphs and Automorphisms of the Hypercube

Consider the set $\mathcal{G}_v$ of all finite simple graphs on a given set of $v$ vertices. Let $m={v\choose 2}$ for sake of notation. Given an identification of $\{1,\dots,m\}$ with the set of ...
1
vote
1answer
154 views

How to uniquely define a tree? [closed]

In an undirected unlabled graph $G=(V,E)$, we want to find a tree as a subgraph, such that the graph can be decomposed into edge disjoint trees(all the tress are isomorphic). How to define such a tree ...
1
vote
1answer
73 views

Probability of paths to the boundary of a tree

Let $G_n$ be the $4$-regular tree of depth $n$, that is to say the finite graph given by the ball of radius $n$ in the Cayley graph of the free group on two generators. By the root I mean the vertex ...
2
votes
1answer
102 views

VLSI circuit embeddings

In the following paper by Valiant http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...
3
votes
0answers
119 views

Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
6
votes
1answer
316 views

Graphs in which any two odd cycle have a common vertex

Let $G$ be a graph in which any two odd cycles have a common vertex. It is easy to see that $\chi(G)\leq 5$ (choose minimal odd cycle $C$, use two colors for $G\setminus C$ and three colors for $C$). ...
0
votes
0answers
105 views

Is there any result on the homomorphic images of hypercube graphs?

Let $Q_n$ be a hypercube graph and $\phi: Q_n\to G$ a surjective simplicial graph morphism i.e. if $u,v$ are adjacent vertices in $Q_n$ then either $\phi(u)=\phi(v)$ or $\phi(u),\phi(v)$ are adjacent. ...
6
votes
1answer
217 views

Graph with group structure?

Is there any established theory of graphs which themselves are groups? I don't mean Cayley graphs or "graphs of groups". I mean a graph whose set of vertices forms a group, where the group operation ...
3
votes
1answer
200 views

Planarity of infinite graphs

Let $G$ be a graph with disjoint copies of $K_{1,3}$. Prove that if there are uncountably many copies of $K_{1,3}$ in $G$, then $G$ is not planar. I have a proof of this statement by ...
7
votes
1answer
272 views

Chromatic numbers of nowhere dense graphs

Given $c\in (0,1)$ and a graph $G=(V,E)$ such that any subset $U\subset V$ contains an independent subset of cardinality at least $c|U|$. Does it allow to bound the chromatic number $\chi(G)$ by the ...
16
votes
0answers
264 views

Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture. But for bigger Ramsey ...
4
votes
0answers
78 views

Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
11
votes
1answer
220 views

What is the chromatic number of the “conic hypergraph” on a non-singular plane cubic?

Can we color the points of a complex non-singular plane cubic curve with finitely many colors so that no conic intersects the curve at 6 distinct points of the same color? If so, what is the smallest ...
6
votes
2answers
130 views

Critical with respect to chromatic, but not Hadwiger number

For any simple, undirected graph $G=(V,E)$ where $V$ is finite, we define the Hadwiger number $\eta(G)$ to be the maximum $n$ such that $K_n$ is a minor of $G$. Is there a graph $G$ on such that ...
3
votes
2answers
63 views

Is there an algorithm for generating sets of routes that satisfy edge volume constraints?

I have reduced a problem I'm working on to something resembling a graph theory problem, and my limited intuition tells me that it's not so esoteric that only I could have ever considered it. I'm ...
1
vote
2answers
56 views

Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
2
votes
1answer
51 views

Simple decomposition of $K_{2n}-I$ into hamiltonian cycles

http://mathworld.wolfram.com/HamiltonDecomposition.html In the 1890s, Walecki showed that complete graphs K_n admit a Hamilton decomposition for odd n, and decompositions into Hamiltonian cycles ...
8
votes
0answers
130 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 ...
-2
votes
1answer
86 views

Graphs such that contracting an edge decreases the chromatic number [closed]

Let $G = (V,E)$ be a finite, simple, undirected, connected graph, such that contracting an edge reduces the chromatic number. Does this imply that $G$ is complete?
2
votes
1answer
163 views

Is there anything similar to the four color theorem for 3-dimensional objects?

From Wikipedia: In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more ...
5
votes
1answer
141 views

Closeness graph of a topological space

Let $(X,\tau)$ be a topological space. We say that $x, y \in X$ are close if for every neighborhood $U$ of $x$ and $V$ of $y$ we have $U\cap V \neq \emptyset$. Let $E$ be the set of $\{x,y\}$ where ...
7
votes
1answer
258 views

A matching that covers vertices with maximum degree

We have a graph G with maximum degree $\Delta$. The induced subgraph on vertices with degree equal to $\Delta$ is a bipartite graph (while the original graph is not). Prove that G has a matching that ...
-1
votes
1answer
81 views

Shortest path problem [closed]

Say that $G'$ is a graph re-weighted from $G$ using the rule: $w' (u, v) = w(u, v) − f(u) + f(v)$, where $f$ always produce the positive results for any nodes. Can we prove that the shortest path ...
7
votes
0answers
65 views

Are graphs with sparse $r$-balls necessarily sparse?

Let $G$ be an unweighted undirected graph with the following property: For some integer $r$, for all nodes $v$, we have $$\frac{\sum \limits_{u \in B(v, r)} \deg(u)}{|B(v, r)|} \le D$$ where $B(v, r) ...
1
vote
0answers
106 views

Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)? To make the question as self-contained as ...
7
votes
4answers
258 views

Graph homomorphisms and line graph

If $G,H$ are simple, undirected graphs, we say that they are in a hom(omorphism)-relation if there is a graph homomorphism from $G$ to $H$ or from $H$ to $G$. For any graph $G$ let $L(G)$ denote its ...
6
votes
1answer
197 views

Given k, what is the minimum n such that n choose n/2 is greater than k? [closed]

I'm not an expert in combinatorics, but it sometimes comes up in my research with students in computer science (which is already pretty far away from my speciality of abstract homotopy theory). I just ...
7
votes
0answers
125 views

De Bruijn sequence inside De Bruijn sequence

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$. What is ...
5
votes
2answers
207 views

How can I prove that these two graph coloring problems are polynomial time equivalent?

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$. ...