All Questions
10 questions
2
votes
1
answer
100
views
Clique number and a special partition
Let $G=(V,E)$ be a finite, simple, undirected, connected graph, and let $\omega(G)$ denote its clique number. Assume that $G$ has a partition into $m$ independent subsets $U_1,\dots, U_m$ such that ...
- 21
1
vote
0
answers
65
views
Partitioning antidirected trees with bounded degree, such that the graph induced by the partition is a constant antidirected tree
Given a partition of the vertices of a graph, we can define an auxiliary graph which conveys information about the edges between sets of the partition. This defines a graph with vertex set equal to ...
- 71
3
votes
1
answer
254
views
Partition graph so every cycle lies in single subgraph
I'm trying to decompose an arbitrary undirected graph G into minimal subgraphs so that no cycle of the original graph does cross the boundaries of a subgraph. The subgraphs are defined by a partition ...
- 133
5
votes
1
answer
406
views
What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?
Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?.
Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=...
1
vote
1
answer
85
views
Enumerating isomorphic subgraphs
For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ ...
- 2,506
1
vote
1
answer
102
views
Existence of a set partition satisfying some restriction
I am looking in the literature for references to combinatorial result of the kind of the one below. I am quite sure they (or some variations of them) should have been studied intensively, but now I am ...
- 51
6
votes
2
answers
573
views
Terminology in combinatorics
I met the following two combinatorial concepts during a study outside of combinatorics. I am wondering if there are common terminologies in combinatorics.
A finite graph $G$ has the following ...
- 75
1
vote
1
answer
208
views
Sequences that represent different drawing of chords?
In combinatorics, there are special kinds of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually, my question is motivated by ...
6
votes
0
answers
657
views
Unique domino tiling
Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset $S$ of the $xy$-plane is star-convex if there ...
- 1,090
20
votes
6
answers
879
views
Hamiltonian paths where the vertices are integer partitions
I have been working on this problem for several months now but have not made much progress. It concerns the set of all integer partitions of n.
Let the vertices of the graph G=G(n) denote all the p(n) ...
- 323