Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2023

Fall 2022

December 8 L. Wagstrom, URI Equitable Choosability of the Disjoint Union of Stars

Abstract: An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. We investigate the list coloring analogue, as introduced by Kostochka, Pelsmajer, and West (2003), which prescribes only an upper bound on the size of each color class in the list coloring. A graph on n vertices is equitably k-choosable if it has a proper list coloring whenever each vertex has a list of size k so that each color is used on at most n/k vertices rounded up. It is known that if two vertex disjoint graphs are equitably k-choosable, their disjoint union may not necessarily be equitably k-choosable. Also, unlike many other variants of list coloring problems, a complete characterization of equitably 2-choosable graphs is not known, and in general not much is known about equitable k-choosability for small k. Here we study the equitable choosability of the disjoint union of stars for arbitrary k. Perhaps surprisingly, since most coloring problems with 2 colors or on stars tend to be easy, we show that determining whether the disjoint union of n stars is equitably 2-colorable is NP-complete. We show that there are only 14 equitably 2-choosable graphs that are the disjoint union of two stars, unlike the infinitely many such equitably 2-colorable graphs, by completely determining when the disjoint union of two arbitrary stars is equitably 2-choosable. We also completely determine when the disjoint union of n identical stars is equitably 2-choosable. Finally, we prove a sufficient condition for the equitable k-choosability of two stars for arbitrary k, and discuss its sharpness. This is joint work with Hemanshu Kaul and Jeffery Mudrock.

December 1 K. Collins, Wesleyan University, Middletown CT Lattice of Block Representations of Split Graphs

Abstract: The degree sequence $D$ of a graph $G$ can be divided into two strictly decreasing integer sequences, $A$ and $B$. These provide the block representation $[A|B]$ of $D$. A graph is a split graph if its vertex set can be partitioned into a clique and a stable set. Membership in the class of split graphs can be determined from degree sequences, and consequently from block representations. In this talk, we use block representations to characterize membership in additional graph classes, including balanced and unbalanced split graphs and pseudo-split graphs. We also discuss features of the poset (under the relation majorization) whose elements are the blocks representing all split graphs with a fixed number of edges, and show that if a maximum and a minimum element are added to it, the result is a lattice. We characterize its meets and joins, provide a natural partition into similarly defined subposets (called amphoras), and use this partition to prove upward and downward closure results for blocks arising from several different families of graphs. This is joint work with Ann N. Trenk, Wellesley College, and Rebecca Whitman, UC Berkeley. Host Mike Barrus.

December 8	L. Wagstrom, URI	Equitable Choosability of the Disjoint Union of Stars
		Abstract: An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. We investigate the list coloring analogue, as introduced by Kostochka, Pelsmajer, and West (2003), which prescribes only an upper bound on the size of each color class in the list coloring. A graph on n vertices is equitably k-choosable if it has a proper list coloring whenever each vertex has a list of size k so that each color is used on at most n/k vertices rounded up. It is known that if two vertex disjoint graphs are equitably k-choosable, their disjoint union may not necessarily be equitably k-choosable. Also, unlike many other variants of list coloring problems, a complete characterization of equitably 2-choosable graphs is not known, and in general not much is known about equitable k-choosability for small k. Here we study the equitable choosability of the disjoint union of stars for arbitrary k. Perhaps surprisingly, since most coloring problems with 2 colors or on stars tend to be easy, we show that determining whether the disjoint union of n stars is equitably 2-colorable is NP-complete. We show that there are only 14 equitably 2-choosable graphs that are the disjoint union of two stars, unlike the infinitely many such equitably 2-colorable graphs, by completely determining when the disjoint union of two arbitrary stars is equitably 2-choosable. We also completely determine when the disjoint union of n identical stars is equitably 2-choosable. Finally, we prove a sufficient condition for the equitable k-choosability of two stars for arbitrary k, and discuss its sharpness. This is joint work with Hemanshu Kaul and Jeffery Mudrock.
December 1	K. Collins, Wesleyan University, Middletown CT	Lattice of Block Representations of Split Graphs
		Abstract: The degree sequence $D$ of a graph $G$ can be divided into two strictly decreasing integer sequences, $A$ and $B$. These provide the block representation $[A\|B]$ of $D$. A graph is a split graph if its vertex set can be partitioned into a clique and a stable set. Membership in the class of split graphs can be determined from degree sequences, and consequently from block representations. In this talk, we use block representations to characterize membership in additional graph classes, including balanced and unbalanced split graphs and pseudo-split graphs. We also discuss features of the poset (under the relation majorization) whose elements are the blocks representing all split graphs with a fixed number of edges, and show that if a maximum and a minimum element are added to it, the result is a lattice. We characterize its meets and joins, provide a natural partition into similarly defined subposets (called amphoras), and use this partition to prove upward and downward closure results for blocks arising from several different families of graphs. This is joint work with Ann N. Trenk, Wellesley College, and Rebecca Whitman, UC Berkeley. Host Mike Barrus.