book chapter · Princeton University Press eBooks · 2017

Synchronizing Graphs

Arthur T. Benjamin, Gary Chartrand, Ping Zhang

Cited by 0Abstract and details only

Abstract

This chapter considers a new type of graph coloring known as edge coloring. It begins with a discussion of an idea by Scottish physicist Peter Guthrie Tait that led to edge coloring. Tait proved that the regions of every 3-regular bridgeless planar graph could be colored with four or fewer colors if and only if the edges of such a graph could be colored with three colors so that every two adjacent edges are colored differently. Tait thought that he had found a new way to solve the Four Color Problem. The chapter also examines the chromatic index of a graph, Vizing's Theorem, applications of edge colorings, and a class of numbers in graph theory called Ramsey numbers. Finally, it describes the Road Coloring Theorem which deals with traffic systems consisting only of one-way streets in which the same number of roads leave each location.

Cite this paper

APA 7

Benjamin, A. T., Chartrand, G., & Zhang, P. (2017). Synchronizing Graphs. Princeton University Press eBooks. https://doi.org/10.23943/princeton/9780691175638.003.0012

MLA 9

Benjamin, Arthur T., et al. “Synchronizing Graphs.” Princeton University Press eBooks, 2017, https://doi.org/10.23943/princeton/9780691175638.003.0012.

Chicago

Benjamin, Arthur T., Gary Chartrand, and Ping Zhang. 2017. “Synchronizing Graphs.” Princeton University Press eBooks. https://doi.org/10.23943/princeton/9780691175638.003.0012.

Harvard

Benjamin, A.T., Chartrand, G. and Zhang, P. (2017) ‘Synchronizing Graphs’, Princeton University Press eBooks. Available at: https://doi.org/10.23943/princeton/9780691175638.003.0012.

BibTeX

@incollection{benjamin2017synchronizing,
  title = {{Synchronizing Graphs}},
  author = {Benjamin, Arthur T. and Chartrand, Gary and Zhang, Ping},
  booktitle = {Princeton University Press eBooks},
  year = {2017},
  doi = {10.23943/princeton/9780691175638.003.0012}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.