# Graph coloring; chromatic number of graph

The three questions are stated in an attached .doc file (1.doc).

In part 1, a diagram is given, and whether the object depicted in the diagram is a graph is to be determined.

In part 2, a graph is given and its chromatic number is to be determined.

In part 3, a graph is given and the number of colors needed to color the regions of the graph (to ensure that adjacent regions have different colors) is to be determined.

© BrainMass Inc. brainmass.com October 24, 2018, 9:30 pm ad1c9bdddfhttps://brainmass.com/math/graphs-and-functions/graph-coloring-chromatic-number-of-graph-128936

#### Solution Preview

Complete solutions are given in an attached .doc file (1-Solution.doc).

In part 1, it is determined that the objected depicted in the given diagram is a graph; its vertex set and edge set are presented.

In part 2, the definition of chromatic ...

#### Solution Summary

The question of whether the object depicted in the given diagram in part 1 is a graph is answered. A detailed determination of the chromatic number of the graph in part 2 is presented, as is a detailed determination of the number of colors needed in part 3 (to ensure that adjacent regions have different colors). The definition of chromatic number of a graph is reviewed.

Question on chromatic number of graph, adjacency matrix and list.

Please see attached questions.

This is three questions.

Question #1 - find the chromatic number of the graph.

Question #2 - It might be supposed that if a graph has a large number of vertices and

each vertex has a large degree, then the chromatic number would have to be large. Show

that this conjecture is incorrect by constructing a graph with at least 12 vertices, each of

degree at least 3, that is chromatic number 2.

Need Attached Graph in editable format, i.e. xls, doc, etc.

Question #3 - Find the adjacency matrix and adjacency list for the directed graph in the

indicated exercise. Order the vertices according to alphabetical order.

Let S - {1,2,4,8} and R = {(1,8), (2,4), (8,2), (4,1), (2,2), (8,1)} be the relation

defined S. Draw the directed multigraph of this relation. Need Attached Graph in

editable format, i.e. xls, doc, etc.