Purchase Solution

chromatic number of graph and adjacency matrix

Not what you're looking for?

Ask Custom Question

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.

Attachments
Purchase this Solution
Solution Summary

Basics of chromatic number of graph, adjacency matrix and list are described.

Solution Preview

See attached file for diagrams to go along with the solution.

Answer: 1

The chromatic number of a graph is the least number of colors required to do coloring of that graph or more clearly we can say that the chromatic number of a graph G is the smallest number of colors needed to color the vertices of G such that no two adjacent vertices share the same color.

In the given graph, if we color vertex A with ...

Purchase this Solution
Free BrainMass Quizzes
Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Probability Quiz

Some questions on probability

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

View More Free Quizzes
Related BrainMass Solutions

  • Adjacency matrix, Order and Valency

    99398 Graphs : Adjacency Matrix, Order and Valency Let A be the adjacency matrix of a regular graph of order v and valency k. Let J be the all-ones matrix of the same order.

  • Adjacency Matrix for Cn

    Here is the definition of the adjacency matrix A of a graph G. It is an n x n matrix, where n is the number of vertices of G.

  • Adjacency matrix

    23480 Adjacency Matrix - Graphs and Their Representations Describe the adjacency matrix for Kn, the simple complete graph with n nodes. Please see the attachment.

  • Ordered Pair, Adjacency Matrix and Graph Representation : C4 and W5

    Since C4 and W5 are undirected graph, we only need to give their adjacent matrix which is a representation of a graph itself. See above graph.

  • Graphs and their adjacency matrices. Trees

    Part I: Adjacency Matrix and Shortest Path Construct a graph based on the adjacency matrix that appears below.

  • Directed graphs

    The directed graph is shown below. The adjacency matrix is This shows how to find the corresponding directed graph and adjacency matrix for a given relation.

  • Adjacency Matrix to Adjacency List translation

    319184 Adjacency Matrix to Adjacency List Translation Find an algorithm to translate the representation of a graph from adjacency matrix to adjacency list.

  • Primitive functions on graph represented by adjacency matrix

    327090 Primitive functions on graph represented by adjacency matrix Modify the program that implements a 6x6 adjacency matrix for a graph. Remember that an adjacency matrix is a two-dimensional array.

  • Graph and describe adjacency matrix

    272203 Graph and describe adjacency matrix Assume that a graph uses and adjacency matrix to represent the edges. Describe how you would update the matrix for the following algorithms. (a). Insert an edge (b). Insert a new vertex (c).

View More Related Solutions