Coloring problems in graph theory

dc.contributor.advisor Berard Lidicky
dc.contributor.advisor Steve Butler Moss, Kevin
dc.contributor.department Mathematics 2018-08-11T06:22:00.000 2020-06-30T03:03:30Z 2020-06-30T03:03:30Z Sun Jan 01 00:00:00 UTC 2017 2001-01-01 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/
dc.identifier.articleid 6390
dc.identifier.contextkey 11051413
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/15383
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 20:40:03 UTC 2022
dc.source.bitstream archive/|||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 Mathematics dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
833.27 KB
Adobe Portable Document Format
No Thumbnail Available
7.1 MB
Plain Text