Date Thesis Awarded


Document Type

Honors Thesis

Degree Name

Bachelors of Science (BS)




Gexin Yu

Committee Member

Marguerite Mason

Committee Member

Rex Kincaid


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 (c1, c2,…ck)-coloring of graph G from G to {1,2,…k} such that for every i, 1≤ i ≤ k, G[Vi] has maximum degree at most ci, where G[Vi] 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.