Browsing Combinatorics and Optimization by Subject "list coloring"

Now showing items 1-3 of 3

Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm

Kelly, Thomas (University of Waterloo, 2019-08-09)

Many of the most celebrated and influential results in graph coloring, such as Brooks' Theorem and Vizing's Theorem, relate a graph's chromatic number to its clique number or maximum degree. Currently, several of the most ...
Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph

Hajebi, Sepehr; Li, Yanjia; Spirkl, Sophie (Society for Industrial and Applied Mathematics, 2022-08-30)

For a positive integer r and graphs G and H, we denote by G+H the disjoint union of G and H and by rH the union of r mutually disjoint copies of H. Also, we say G is H-free if H is not isomorphic to an induced subgraph of ...
Thomassen’s 5-Choosability Theorem Extends to Many Faces

Nevin, Joshua (University of Waterloo, 2021-09-10)

We prove in this thesis that planar graphs can be L-colored, where L is a list-assignment in which every vertex has a 5-list except for a collection of arbitrarily large faces which have 3-lists, as long as those faces ...