Approximate edge 3-coloring of cubic graphs

Show full item record

Please use this identifier to cite or link to this item:

Title: Approximate edge 3-coloring of cubic graphs
Author: Gajewar, Amita Surendra
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.
Type: Thesis
Date: 2008-07-10
Publisher: Georgia Institute of Technology
Subject: Deterministic random walk
Cubic graphs
Edge 3-coloring
Propp model
Graph coloring
Graph algorithms
Department: Computing
Advisor: Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran
Degree: M.S.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
gajewar_amita_s_200808_mast.pdf 184.3Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record