What Is the Minimum Number of Rooms Needed in a Hotel Graph Problem?

[evinda]

Hello! (Smile)

I am looking at the following exercise:

There are $1000$ people in a hotel and each person knows at most $3$ people.
We want to find the minimum number of rooms,that are needed,so that no person is at the same room with other people,that he knows.

I thought that I could substract from the total number of rooms without restrictions, the number of rooms,that are needed,so that each person is at the same room with persons that he knows.. But...how can I find the last number..?

 

[chisigma]

Hello! (Smile)

I am looking at the following exercise:

There are $1000$ people in a hotel and each person knows at most $3$ people.
We want to find the minimum number of rooms,that are needed,so that no person is at the same room with other people,that he knows.

I thought that I could substract from the total number of rooms without restrictions, the number of rooms,that are needed,so that each person is at the same room with persons that he knows.. But...how can I find the last number..?

Let suppose that the set of 1000 people is devided into four subset...

a) the subset which contains all people knowing three other people, it is composed by groups of four people...

b) the subset which contains all people knowing two other people, it is composed by groups of three people...

c) the subset which contains all people knowing one other person, it is composed by groups of two people...

d) the subset which contains all people knowing no other people, it is composed by groups of one person...

If You use four rooms, You first divide the components of each group in a) into them and then You proceed with the component of each group of b) and so one... the minimum number of rooms is four...

Kind regards

$\chi$ $\sigma$

 

[caffeinemachine]

Hello! (Smile)

I am looking at the following exercise:

There are $1000$ people in a hotel and each person knows at most $3$ people.
We want to find the minimum number of rooms,that are needed,so that no person is at the same room with other people,that he knows.

I thought that I could substract from the total number of rooms without restrictions, the number of rooms,that are needed,so that each person is at the same room with persons that he knows.. But...how can I find the last number..?

We can formulate the question in graph theoretic terms.

A graph is said to be good if it has a $1000$ vertices and if each of its vertices has degree atmost 3.

Let $\mathcal G$ be the set of all the good graphs.

The question is asking us to find $\max_{G\in \mathcal G} \chi(G)$, where $\chi(G)$ is the chromatic number of the graph $G$.

These are my first thoughts. Let me think about how to actually find the above mentioned quantity.

Continuation: Using Brook's Theorem [Brooks' theorem - Wikipedia, the free encyclopedia] it can be easily seen that the required number is $4$.