Back to search

Georgia Institute of Technology

Approximate edge 3-coloring of cubic graphs

Abstract

dc:description.abstract

The work in this thesis can be divided into two different parts. In the first part, we suggest an approximate edge 3-coloring polynomial time algorithm for cubic graphs. For any cubic graph with n vertices, using this coloring algorithm, we get an edge 3-coloring with at most n/3 error vertices. In the second part, we study Jim Propp's Rotor-Router model on some non-bipartite graph. We find the difference between the number of chips at vertices after performing a walk on this graph using Propp model and the expected number of chips after a random walk. It is known that for line of integers and d-dimenional grid, this deviation is constant. However, it is also proved that for k-ary infinite trees, for some initial configuration the deviation is no longer a constant and say it is D. We present a similar study on some non-bipartite graph constructed from k-ary infinite trees and conclude that for this graph with the same initial configuration, the deviation is almost (k²)D.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gajewar, Amita Surendra
Advisor dc:contributor.advisor
  • Lipton, Richard J.
Committee members dc:contributor.committeemember
  • Basu, Sumit
  • Bobick, Aaron
  • Ellis, Dan
  • Isbell, Charles
  • Weinberg, Gil

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/29735

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gajewar, Amita Surendra. Approximate edge 3-coloring of cubic graphs. Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735