Back to search

Georgia Institute of Technology

Forbidden subgraphs and 3-colorability

Abstract

dc:description.abstract

Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such examples can be found in the book of Hansen and Marcotte. Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem, even for triangle-free graphs. Intuitively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic number at least k. Thus, restricting girth alone does not help bound the chromatic number. However, if we forbid certain tree structure in addition to girth restriction, then it is possible to bound the chromatic number. Randerath determined several such tree structures, and conjectured that if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a star K1,4 with two branches subdivided once. The main result of this thesis is that Randerath’s conjecture is true for graphs with odd girth at least 7. We also give a proof that Randerath’s conjecture holds for graphs with maximum degree 4.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ye, Tianjun
Advisor dc:contributor.advisor
  • Yu, Xingxing
Committee members dc:contributor.committeemember
  • Chen, Guantao
  • Tetali, Prasad
  • Thomas, Robin
  • Trotter, William

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Ye, Tianjun. Forbidden subgraphs and 3-colorability. Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/48986