Back to search

University of Waterloo

List Coloring Some Classes of 1-Planar Graphs

Abstract

dc:description.abstract

In list coloring we are given a graph G and a list assignment for G which assigns to each vertex of G a list of possible colors. We wish to find a coloring of the vertices of G such that each vertex uses a color from its list and adjacent vertices are given different colors. In this thesis we study the problem of list coloring 1-planar graphs, i.e., graphs that can be drawn in the plane such that any edge intersects at most one other edge. We also study the closely related problem of simultaneously list coloring the vertices and faces of a planar graph, known as coupled list coloring. We show that 1-planar bipartite graphs are list colorable whenever all lists are of size at least four, and further show that this coloring can be found in linear time. In pursuit of this result, we show that the previously known edge partition of a 1-planar graph into a planar graph and a forest can be found in linear time. A wheel graph consists of a cycle of vertices, all of which are adjacent to an additional center vertex. We show that wheel graphs are coupled list colorable when all lists are of size five or more and show that this coloring can be found in linear time. Possible extensions of this result to planar partial 3-trees are discussed. Finally, we discuss the complexity of list coloring 1-planar graphs, both in parameterized and unparameterized settings.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Barr, Sam
Advisor dc:contributor.advisor
  • Biedl, Therese

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/17813

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Barr, Sam. List Coloring Some Classes of 1-Planar Graphs. University of Waterloo, 2021. http://hdl.handle.net/10012/17813