András London1
1Institute of Informatics, University of Szeged, Szeged, Hungary
Abstract:

We study edge partitions of a bipartite graph into induced-2K2-free bipartite graphs, i.e. into Ferrers (chain) graphs. We define fp(G) as the minimum number of parts in such a partition. We prove general lower and upper bounds in terms of induced matchings and Dilworth widths of neighborhood posets. We compute the parameter exactly for paths and even cycles, and we exhibit separations showing that the induced-matching lower bound and the width upper bound can both be far from tight. We also record a simple host-induced conflict-graph lower bound, present a 01 matrix viewpoint, and add some complexity remarks.

Johann Cigler1, Hans-Christian Herbig2
1Department of Mathematics, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria
2Departamento de Matematica Aplicada, Universidade Federal do Rio de Janeiro, Av. Athos da Silveira Ramos 149, Centro de Tecnologia – Bloco C, CEP: 21941-909, Rio de Janeiro, Brazil
Abstract:

We present a proof of a conjecture of Goh and Wildberger on the factorization of the spread polynomials. We indicate how the factors can be effectively calculated and exhibit a connection to the factorization of Fibonacci numbers into primitive parts.