I have a question related to graph theory. First, I want to state that I am not a mathematician or computer scientist, but a psychologist doing research on cognitive processing related to computer science concepts.
We plan conducting a study with human participants on scheduling problems with graph visualizations as aids for solving the problems. I am currently working on generating the material, i.e. the graphs that underlie the problems.
In psychological experiments we always aim at keeping as many properties of the material constant (controlled) as possible. In this case, we want to restrict the experiment to graphs with 6 vertices and around 8 edges to have some managable complexity of the problems for laypeople.
Now, those graphs are probably all going to be planar and my attempts in manually constructing them all the time result in graphs that have the chromatic number 3 which might be "boring" for participants after a few examples, so I would like to learn what is required to construct graphs with 6 vertices and chromatic number 4. Are simply more edges necessary? (Ideally, the graphs would not be disconnected.) Do I have to include K4 as a subgraph?
In German Wikipedia I found some statement that roughly translate to this: "What is the chromatic number of a planar graph? The four-color theorem states that the chromatic number of a planar graph is at most 4. If the graph does not contain a triangle, it is even 3-node colorable." What is a triangle in this sense? 3 nodes connected by lines (forming a triangle in the geometric sense) can't be right ... Is it rather K4?
I would be very grateful for some helpful hints regarding my problem.
As illustrative examples of what I have tried so far see the following:
Both graphs have 6 vertices and 8 edges. The left graph has several "triangles" and can still be coloured using three colours. The right one requires four colours since it contains K4.
As from Grötzsch's theorem, we need to have a triangle in our graph. The only reason is that we can exploit this by adding another point and connecting it to all of the points of the triangle.
We can see that the configuration below has a chromatic number of 4 and consists of 4 points:
You now can add 2 extra points to get a total of 6 points, adding any configuration you want.
For example,