#### Date Thesis Awarded

5-2015

#### Document Type

Honors Thesis

#### Degree Name

Bachelors of Science (BS)

#### Department

Mathematics

#### Advisor

Gexin Yu

#### Committee Member

Marguerite Mason

#### Committee Member

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 _{1}, c_{2},…c_{k})-*coloring of graph

*G*from

*G*to

*{1,2,…k}*such that for every

*i, 1*

*≤ i*

*≤ k, G[V*has maximum degree at most

_{i}]*c*where

_{i},*G[V*represents the subgraph induced by the vertices colored with

_{i}]*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.* Paper 131.

http://publish.wm.edu/honorstheses/131