In this post I introduce a family of graphs that provides examples of Q1 graphs for all composite orders. If n is composite then it has a partition of the form m+m+…+m, where 1<m<n. For future convenience I am going to start using a different notation for partitions. Rather than m+m+…+m, I will write (m,m,…,m). I claim that (m,m,…,m) is a Q1 partition and the graph below is a Q1 graph that prohibits it
If m is odd, then m=2k+1 for some k and the graph looks like this:
1) That the partition (m,m,…,m) is a prohibited partition, and
2) that all other partitions P are allowed.
First, suppose that (m,m,…,m) were an allowed partition. Then consider the vertex labeled a below. It must be contained in a connected subgraph of order m (one of the monochromatic subgraphs of a good coloring). The the set of vertices labeled A must be in the same subgraph with a (that is colored the same color). A only contains k+1 vertices, so we need more colored the same color as a. At this point there appears to be a choice: should the vertex labeled b be the same color as a? If it is the same color, then the row of vertices on the bottom right will be connected to no other vertices other than each other, but this would be a monochromatic subgraph of at most k vertices, which would not make a good partition.
Now for part 2) All other partitions P are allowed. If the parts (coordinates) of P are not all m then there is at least one (call it i) that is not equal to m. There are three subcases: a) i<k+1, b) k<i<m or c) m<i.
Subcase a) Let a monochromatic subgraph of size i be the one circled below. As shown by the green line, the remaining graph contains a Hamiltonian path and so is Q1 and can be partitioned according to the remainder of P.
Subcase b) Let a monochromatic subgraph of size i be the one circled in red below. Again, a Hamiltonian path for the remainder is shown in green, so we are done as in the previous subcase.
Subcase c) Let a monochromatic subgraph of size i be the one circled in red below. What remains is a path, and we are done.
We are now left to wonder for which prime orders there are Q1 graphs (we have seen that for orders 2 and 3 there are Q1 graphs and for orders 5 and 7 there are not. We have also seen several other prime orders for which there are Q1 graphs.) My next post will address this issue further.