2 citations · 2 across the 6 of their papers we have counts for
6 papers
Algorithmic Applications of Tyshkevich's Graph Decomposition: A Primer and a Toolkit
Christine T. Cheng, Chelsea Ann Lambert
A graph that is completely determined by its degree sequence is called a unigraph. In 2000, Regina Tyshkevich published one of the most important papers on unigraphs. There are two…
Tyshkevich's Graph Decomposition and the Distinguishing Numbers of Unigraphs
Christine T. Cheng
A -labeling $ϕ: V(G) \rightarrow \{1, 2, \hdots, c \}$ of graph is distinguishing if, for every non-trivial automorphism of , there is some vertex so that $ϕ(v) \…
Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth
Christine T. Cheng, Will Rosenbaum
In this paper, we consider the problem of counting and sampling structures in graphs. We define a class of "edge universal labeling problems"---which include proper -colorings,…
Stable Matchings with Restricted Preferences: Structure and Complexity
Christine T. Cheng, Will Rosenbaum
It is well known that every stable matching instance has a rotation poset that can be computed efficiently and the downsets of are in one-to-one correspondence wi…
Split Graphs and Nordhaus-Gaddum Graphs
Christine Cheng, Karen L. Collins, Ann Trenk
A graph G is an NG-graph if χ(G) + χ(G complement) = |V(G)| + 1. We characterize NG-graphs solely from degree sequences leading to a linear-time recognition algorithm. We also expl…
On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach
V. Arvind, Christine T. Cheng, Nikhil R. Devanur
A vertex k-labeling of graph G is distinguishing if the only automorphism that preserves the labels of G is the identity map. The distinguishing number of G, D(G), is the smallest…