1 citations · 1 across the 7 of their papers we have counts for
7 papers
Almost perfect graph classes
Cicely Henderson, Hidde Koerts, Taite LaGrange +4
A graph is perfect if for each induced subgraph of . In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem.…
Maximum -colourable induced subgraphs in -free graphs
Cicely Henderson, Evelyne Smith-Roberge, Sophie Spirkl +1
We show that for any nonnegative integer , the Weighted Maximum List--Colourable Induced Subgraph problem can be solved in polynomial time for input graphs that do not contai…
Graphs Identifiable by Degree Sequence and Chromatic Number
R. Whitman
Unigraphs are graphs identifiable up to isomorphism from their degree sequences. Given a class of graphs, we define the class of -unigraphs to be graphs…
Trail Trap: a variant of Partizan Edge Geography
Calum Buchanan, MacKenzie Carr, Alexander Clifton +4
We study a two-player game played on undirected graphs called {\sc Trail Trap}, which is a variant of a game known as {\sc Partizan Edge Geography}. One player starts by choosing a…
Hereditary Nordhaus-Gaddum Graphs
Vaidy Sivaraman, Rebecca Whitman
Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number of a graph and its complement is at most . The Nordhaus-Gaddum graphs are the class of graphs…
The Hereditary Closure of the Unigraphs
Michael D. Barrus, Ann N. Trenk, Rebecca Whitman
A graph with degree sequence is a \emph{unigraph} if it is isomorphic to every graph that has degree sequence . The class of unigraphs is not hereditary and in this paper we…
Split graphs and Block Representations
Karen L. Collins, Ann N. Trenk, Rebecca Whitman
In this paper, we study split graphs and related classes of graphs from the perspective of their sequence of vertex degrees and an associated lattice under majorization. Following…