Relaxation of Planar Graphs With d∆≥2 and No 4-Cycles

Author

Heather A. Hoskins, College of William and MaryFollow

Date Thesis Awarded

5-2015

Access Type

Honors Thesis -- Access Restricted On-Campus Only

Degree Name

Bachelors of Science (BS)

Department

Mathematics

Advisor

Gexin Yu

Committee Members

Marguerite Mason

Rex Kincaid

Abstract

First, let a graph be a set of vertices (points) and a set of edges (lines) connecting these vertices. Further, let a planar graph be a graph that can be represented on the plane without any edges crossing. Define a (c₁, c₂,…c_k)-coloring of graph G from G to {1,2,…k} such that for every i, 1≤ i ≤ k, G[V_i] has maximum degree at most c_i, where G[V_i] represents the subgraph induced by the vertices colored with i. The Four Color Theorem by Appel and Haken (1973) states that all planar graphs are 4-colorable. The Bordeaux Conjecture (2003) postulates that planar graphs with no 5-cycles and without intersecting triangles is 3-colorable. Liu, Li and Yu (2014) proved that planar graphs without intersecting triangles and 5-cycles is (2,0,0) colorable. We prove that all planar graphs without 4-cycles and no less than two edges between triangles is also (2,0,0) colorable.

Recommended Citation

Hoskins, Heather A., "Relaxation of Planar Graphs With d∆≥2 and No 4-Cycles" (2015). Undergraduate Honors Theses. William & Mary. Paper 131.
https://scholarworks.wm.edu/honorstheses/131

Creative Commons License

This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.