Back to search

Georgia Institute of Technology

Coloring graphs with no k5-subdivision: disjoint paths in graphs

Abstract

dc:description.abstract

The Four Color Theorem states that every planar graph is 4-colorable. Hajos conjectured that for any positive integer k, every graph containing no K_{k+1}-subdivision is k-colorable. However, Catlin disproved Hajos conjecture for k>=6. It is not hard to prove that the conjecture is true for k<=3. Hajos' conjecture remains open for k=4 and k=5. We consider a minimal counterexample to Hajos conjecture for k=4. We use Hajos graph to denote such counterexample. One important step to understand graphs containing K5-subdivisions is to solve the topological H problem. We characterize graphs with no topological H, and the characterization is used by He, Wang, and Yu to show that graph containing no K5-subdivisions is planar or has a 4-cut, establishing conjecture of Kelmans and Seymour. Besides the topological H problem, we also obtained some further structural information of Hajos graphs.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Xie, Qiqin
Advisor dc:contributor.advisor
  • Yu, Xingxing
Committee members dc:contributor.committeemember
  • Blekherman, Grigoriy
  • Iliev, Plamen
  • Yu, Josephine
  • Huang, Hao

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Xie, Qiqin. Coloring graphs with no k5-subdivision: disjoint paths in graphs. Doctoral thesis, Georgia Institute of Technology, 2019. http://hdl.handle.net/1853/62659