Back to search

Georgia Institute of Technology

On the Structure of Counterexamples to the Coloring Conjecture of Hajós

Abstract

dc:description.abstract

Hajós conjectured that, for any positive integer k, every graph containing no K_(k+1)-subdivision is k-colorable. This is true when k is at most three, and false when k exceeds six. Hajós' conjecture remains open for k=4,5. We will first present some known results on Hajós' conjecture. Then we derive a result on the structure of 2-connected graphs with no cycle through three specified vertices. This result will then be used for the proof of the main result of this thesis. We show that any possible counterexample to Hajós' conjecture for k=4 with minimum number of vertices must be 4-connected. This is a step in an attempt to reduce Hajós' conjecture for k=4 to the conjecture of Seymour that any 5-connected non-planar graph contains a K_5-subdivision.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zickfeld, Florian
Advisor dc:contributor.advisor
  • Yu, Xingxing
Committee members dc:contributor.committeemember
  • Anurag Singh
  • Tetali, Prasad
  • Thomas, Robin

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Zickfeld, Florian. On the Structure of Counterexamples to the Coloring Conjecture of Hajós. Georgia Institute of Technology, 2004. http://hdl.handle.net/1853/4994