Explore BrainMass

Explore BrainMass

    chromatic number of graph and adjacency matrix

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com December 24, 2021, 7:50 pm ad1c9bdddf


    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 ...

    Solution Summary

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