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

Tariq, Juvaria (Summer 2024)

Permanent URL: https://etd.library.emory.edu/concern/etds/g445cf73z?locale=it
Published

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
Department
Degree
Submission
Language
  • English
Research Field
Parola chiave
Committee Chair / Thesis Advisor
Committee Members
Ultima modifica

Primary PDF

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

Supplemental Files

Thumbnail Title Date Uploaded Actions