Partitions of Graphs VI: Q1 Graphs

This is the sixth in a series.  The first is found here: Part I.  The previous is found here: Part V.

I have defined q(G) to be:

q(G) = p(n) – p(G), where n is the number of nodes in G.

In other words q(G) is the number of partitions prohibited by G.  We’ve seen graphs, G, with p(G)=1, that is with exactly one allowed partition.  In fact we know that the one allowed partition is:

1+1+1+ . . . +1

and the graph consists of n nodes and no edges.  But let’s say that we want a graph, G, with q(G)=1.  I’ll call such a graph a Q1 graph (in fact if q(G)=k lets call it a Qk graph).  It’s not quite as easy to find Q1 graphs as it was to find graphs with p(G)=1.  For one thing it isn’t at all obvious what the one prohibited partition should be.  A first guess might be that the prohibited partition should be n.  This sounds plausible since in some sense the partition n is the alter-ego of the partition 1+1+1+ . . . +1.  Following this lead we should look for graphs that are not connected, but that allow every partition of n other than n.  Indeed, initially we find success:

`     q( o o ) =  1`

and

`     q( o o-o) = 1`

So far so good.  We’ve done n=2 and n=3 (conspicuously skipping n=1, I’ll leave that case for you to ponder), but when we get to n=4 we hit trouble.  If q(G)=1, with the partition 4 prohibited, then 3+1 must be allowed.  That means that for a good coloring there are going to be three nodes that are the same color.  All three nodes have to be part of a connected subgraph, but the other node, the fourth node, can’t be connected to those other three at all.  In other words, the largest connected component of the graph has three nodes.  If it were any bigger it would have four nodes and the whole graph would be connected, which we assumed wasn’t true.  So there is a single solitary node floating all by it’s lonesome in space.  But 2+2 is also allowed (every partition other than 4 is assumed to be allowed) which tells us that each node of G is adjacent to at least one other node (two nodes get colored red, two blue in a good coloring).  But what about our single, solitary node floating in space?  This says that he can’t be single or solitary or floating in space.  You can’t be single, solitary and floating in space when you are closely tethered to your best buddy.  That’s what we call a contradiction, which means that our hypothesis that q(G)=1 with 4 prohibited is impossible.

Of course in a previous post we’ve seen that

```            o
/
q( o-o-o   ) = 1```

with the prohibited partition being 2+2 (This is S4, I’ve drawn it slightly differently here).  It took me some time to see that this is just the first of a whole family of graphs with q(G)=1.

Remark: If n is even, then

```                      o
/
q( o-o-o-...-o-o-o   ) = 1  (n even)```

and the prohibited partition is 2+2+2+ . . . +2.  If n is odd then

```                      o
/
q( o-o-o-...-o-o-o   ) = 0  (n odd)```

Proof: We need to show that if there are an even number of nodes then 2+2+2+ . . . +2 is prohibited and all other partitions are allowed.  To see that 2+2+2+ . . . +2 is prohibited is pretty easy.  What would a good coloring look like?  The node farthest to the right and on the bottom would be some color, let’s say it’s purple.

```                   o
/
o-o-o-...-o-o-o
```

There must be two purple nodes and they have to be adjacent so the next node to the left has to be purple also.

```                   o
/
o-o-o-...-o-o-o```

But where does that leave the top node?  High and dry, without a friend in the world.  In other words it has to be a color other than purple, let’s say orange and it has to have an orange buddy, but there are none to be found.

```                   o    (Which other node should be orange?)
/
o-o-o-...-o-o-o```

So 2+2+2+ . . . +2 is prohibited.  Now we prove that every other partition is allowed.  If P is a partition whose summands are not all 2‘s then either P has a 1 as a summand or P has a summand that is 3 or greater.  We consider thees two cases.  First if P has a 1 as a summand then say that 1 gets colored purple.  Then we color the node on the top purple

```                   o
/
o-o-o-...-o-o-o```

no other node is colored purple, and what remains of the graph is a path, so we will be able to find a good coloring for it.  Here is an example of what I’m talking about.  Say n=8 and P=4+3+1.  We color P: and use this as instructions for coloring the graph.  First we color the top node purple and then we color the first four of the path red and the next four green.

```                 o
/
o-o-o-o-o-o-o```

Here’s another example.  A good coloring of 2+2+2+2+2+1+1:

```                         o
/
o-o-o-o-o-o-o-o-o-o-o```

Let’s address the other case of there being a summand of P greater than or equal to 3.  Say the partition is 6+5+5+2+2+2, (n=22).  We color P: 6+5+5+2+2+2 .  Now we pick one of the summands which is 3 or greater.  Let’s say we pick one of the 5‘s.  We color the 5 nodes farthest to the right the color of that 5.  Let’s say we picked the green 5.  What’s left over is a path.

```                                             o
/
o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o-o```

In general pick any summand larger than 2 and color the right most nodes that color.  What’s left will be a path and allow a good coloring no matter what the other summands are.  This proves that all partitions other than the one consisting entirely of 2’s are allowed.  Finally odd numbers do not have a partition consisting entirely of 2’s, so every partition of an odd number is allowed. QED.

So we have this family of Q1 graphs:

```                   o
/
o-o-o-...-o-o-o```

for even numbers, n.  It turns out there is a similar family of Q1 graphs when n is divisible by 3.  Here it is:

```                   o
/
o-o-o-...-o-o-o-o```

The proof that this is a Q1 graph when n is divisible by 3 (and a Q0 graph otherwise) is similar to the above proof.  The prohibited partition is 3+3+3+ . . . +3.  If P is a partition whose summands are not all 3, then there are three cases to consider: P has 1 as a summand, P has 2 as a summand and P has a summand that is 4 or larger.  Here are three pictures illustrating the three cases respectively.

```                   o
/
o-o-o-...-o-o-o-o```
```                   o
/
o-o-o-...-o-o-o-o```
```                   o
/
o-o-o-...-o-o-o-o```

In each case what is left over is a path, so the rest of the graph can be given a good coloring.

We’ve found two families of Q1 graphs that give us examples for n even and n divisible by 3.  So we have Q1 graphs for all n between 2 and 10 except n=5 and n=7.  In my next post I will address the cases n=5 and n=7.  In subsequent posts n=11 and n=13 will be addressed.

Part VII: The Cases of 5 and 7