53 citations · 218 across the 50 of their papers we have counts for
65 papers
Deciding lettericity is NP-complete, even for four-colorable comparability graphs
Vincent Vatter
We prove that deciding whether a graph has lettericity at most k is NP-complete, even for four-colorable comparability graphs. Our reduction maps a bipartite graph G to the graph o…
Chains and unique transitive orientations of prime graphs
Robert Brignall, Sean Mandrick, Vincent Vatter
We give a short, conceptual proof that prime graphs have at most two transitive orientations, a much-quoted result of Gallai. Our proof uses chains, introduced by Chudnovsky, Kim,…
Permutation Wordle
Samuel Kutin, Lawren Smithline, Vincent Vatter
We introduce a guessing game, ``Permutation Wordle,'' in which a guesser attempts to recover a setter's hidden permutation of the set . In each round, the guesser…
Log-concavity of subsequence counts of words
Vincent Vatter
Given a word over a finite alphabet, consider the sequence that counts, for each length, the number of distinct subsequences of that length. In 1976, Chase proved that this sequenc…
Cyclomatic numbers and permutations
Bridget Eileen Tenner, Vincent Vatter
We show that several apparently different aspects of a permutation are all tied to a single quantity, the cyclomatic number of its inversion graph. Every reduced word for the permu…
Boolean--Eulerian numbers
Miklós Bóna, Vincent Vatter
We study decreasing binary trees in which every vertex with two children is colored red or blue. We construct two bijections. The first, to ordered set partitions into odd-sized bl…