Coloring problems in graph theory

dc.contributor.advisor Berard Lidicky
dc.contributor.advisor Steve Butler
dc.contributor.author Moss, Kevin
dc.contributor.department Mathematics
dc.date 2018-08-11T06:22:00.000
dc.date.accessioned 2020-06-30T03:03:30Z
dc.date.available 2020-06-30T03:03:30Z
dc.date.copyright Sun Jan 01 00:00:00 UTC 2017
dc.date.embargo 2001-01-01
dc.date.issued 2017-01-01
dc.description.abstract <p>We consider two branches of coloring problems for graphs: list coloring and packing coloring. We introduce a new variation to list coloring which we call choosability with union separation: For a graph G, a list assignment L to the vertices of G is a (k,k+t)-list assignment if every vertex is assigned a list of size at least k and the union of the lists of each pair of adjacent vertices is at least k+t. We explore this new variation and offer comparative results to choosability with intersection separation, a variation that has been studied previously.</p> <p>Regarding packing colorings, we consider infinite lattice graphs and provide bounds to their packing chromatic numbers. We also provide algorithms for coloring these graphs. The lattices we color include two-layer hexagonal lattices as well as the truncated square lattice, a 3-regular lattice whose faces have length 4 and 8.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/etd/15383/
dc.identifier.articleid 6390
dc.identifier.contextkey 11051413
dc.identifier.doi https://doi.org/10.31274/etd-180810-5276
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/15383
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/29566
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/15383/0-tiling205D1536x1152.txt|||Fri Jan 14 20:40:03 UTC 2022
dc.source.bitstream archive/lib.dr.iastate.edu/etd/15383/Moss_iastate_0097E_16386.pdf|||Fri Jan 14 20:40:04 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Mathematics
dc.subject.keywords Choosability
dc.subject.keywords Combinatorics
dc.subject.keywords Graph Coloring
dc.subject.keywords Graph Theory
dc.subject.keywords Packing Coloring
dc.supplemental.bitstream tiling205D1536x1152.txt
dc.title Coloring problems in graph theory
dc.type article
dc.type.genre dissertation
dspace.entity.type Publication
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
thesis.degree.discipline Mathematics
thesis.degree.level dissertation
thesis.degree.name Doctor of Philosophy
File
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
Moss_iastate_0097E_16386.pdf
Size:
833.27 KB
Format:
Adobe Portable Document Format
Description:
No Thumbnail Available
Name:
0-tiling205D1536x1152.txt
Size:
7.1 MB
Format:
Plain Text
Description: