Some Cases of Erdős-Lovász Tihany Conjecture Open Access

Abstract

The Erd\H{o}s-Lov\'asz Tihany Conjecture states that any $G$ with chromatic number $\chi(G) = s + t - 1 > \omega(G)$, with $s,t \geq 2$ can be split into two vertex-disjoint subgraphs of chromatic number $s, t$ respectively. We prove this conjecture for pairs $(s, t)$ if $t \leq s + 2$, whenever $G$ has a $K_s$, and for pairs $(s, t)$ if $t \leq 4 s - 3$, whenever $G$ contains a $K_s$ and is claw-free. We also prove the Erd\H{o}s Lov\'asz Tihany Conjecture for the pair $(3, 10)$ for claw-free graphs.

Table of Contents

Contents

1 Introduction

1.1 Notation and Definitions

1.2 Background

1.3 K_{\ell}-Critical Graphs

1.4 Results

1.5 Organization

2 Preliminary Lemmas

3 $K_{\ell}$-critical graphs with $\chi(G)\leq 2\ell +1$

4 Claw-Free Graphs

4.1 Claw-free Graphs with $\chi(G)\leq 5l-4$

4.2 Claw-free Graphs with $\chi(G)=12$

5 Summary and Future Research

Bibliography

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Mathematics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Mathematics
Keyword	Erdos-Lovasz Claw-free Graphs Chromatic number Graph Theory
Committee Chair / Thesis Advisor	Hao Huang, National University of Singapore
Committee Members	Vojtěch Rödl, Emory University Dwight Duffus, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Some Cases of Erdős-Lovász Tihany Conjecture ()	2024-07-05 23:54:01 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions