This is the tenth in a series, the first being found here: Part 1, and the previous here: Part 9.

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

The above picture is ambiguous. I need to tell you how many vertices are in each section. There are two cases. If m is even then m=2k for some k. In that case the graph looks like this:

If m is odd, then m=2k+1 for some k and the graph looks like this:

Proof of claim: To demonstrate that this graph is Q1, I have to convince you of two things:

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.

Therefore, the vertex labeled b is not colored the same color as a, and so there are no other choices for the monochromatic subgraph of a than the one below:

But of course this would leave the vertex labeled c disconnected, this is a contradiction since a good coloring would have c in a monochromatic subgraph of size m.

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.

Pingback: Partitions of Graphs IX: The case of 13 « MATH with my KIDS

Pingback: Partitions of Graphs XI: The Case of all Sufficiently Large n « MATH with my KIDS