Description

Every graph can be colored with one more color than its maximum degree. A well-known theorem of Brooks gives the precise conditions under which a graph can be colored with

Every graph can be colored with one more color than its maximum degree. A well-known theorem of Brooks gives the precise conditions under which a graph can be colored with maximum degree colors. It is natural to ask for the required conditions on a graph to color with one less color than the maximum degree; in 1977 Borodin and Kostochka conjectured a solution for graphs with maximum degree at least 9: as long as the graph doesn't contain a maximum-degree-sized clique, it can be colored with one fewer than the maximum degree colors. This study attacks the conjecture on multiple fronts.

Reuse Permissions
  • 800.58 KB application/pdf

    Download count: 0

    Details

    Contributors
    Date Created
    • 2013
    Resource Type
  • Text
  • Collections this item is in
    Note
    • Partial requirement for: Ph.D., Arizona State University, 2013
      Note type
      thesis
    • Includes bibliographical references (p. 166-171)
      Note type
      bibliography
    • Field of study: Mathematics

    Citation and reuse

    Statement of Responsibility

    by Landon Rabern

    Machine-readable links