Displaying similar documents to “Combinatorics of tripartite boundary connections for trees and dimers.”

Kasteleyn cokernels.

Kuperberg, Greg (2002)

The Electronic Journal of Combinatorics [electronic only]


On the rooted Tutte polynomial

F. Y. Wu, C. King, W. T. Lu (1999)

Annales de l'institut Fourier


The Tutte polynomial is a generalization of the chromatic polynomial of graph colorings. Here we present an extension called the rooted Tutte polynomial, which is defined on a graph where one or more vertices are colored with prescribed colors. We establish a number of results pertaining to the rooted Tutte polynomial, including a duality relation in the case that all roots reside around a single face of a planar graph.

On the proper intervalization of colored caterpillar trees

Carme Àlvarez, Maria Serna (2009)

RAIRO - Theoretical Informatics and Applications


This paper studies the computational complexity of the problem (), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the and a graph layout problem the (). We show a dichotomy: the and the are NP-complete for colored caterpillars of hair length 2, while both problems are in P for colored caterpillars of hair length 2. For the hardness results we provide a reduction from the , while the...