Ljubljana - Leoben Graph Theory Seminar 2014

Covering the edges of a graph by matchings of bounded size

Not scheduled

Velika predavalnica (UP FAMNIT, Koper, Slovenia)

Speaker

Prof. Romeo Rizzi (Universita' di Verona)

Description

Our aim in this talk is to report on a non-mainstream but interesting edge-colouring line of research we were conducting with our coauthor, friend, and colleague, David Cariolaro, prematurely disappeared this January. For me, the talk is also a tribute to David's memory. Yet, I (and David) would hope this to be a lively talk where the few techniques and results we could gather together get exposed, and new agendas of curiosity and enquiry are drawn. A problem he loved: what is the minimum number of perfect matchings which allows to cover every edge of a graph? He, with Hung-Lin Fu, dubbed this number the excessive factorization index of a graph. Its computation is an NP-complete problem and interesting families of regular graphs where this number goes big where described by other authors. A more pratically oriented problem: what if we are allowed to use only matchings of size at most (or precisely) a fixed given natural B? He dubbed this number the excessive (B)-factorization index (the excessive [B]-factorization index, resp.) of a graph. Bipartite graphs: though all of the above factorization indices are NP-complete to compute, together (2010) we gave effective polynomial time algorithms for their determination in the bipartite case. These algorithms work also for multigraphs (parallel edges) and the dependence of their running times in B is also polynomial. Classical edge coloring with color classes of bounded size: in a joint technical paper on Algorithmica (2014), we showed that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes. Though the running time of these algorithms is high (with polynomials in B at the exponent), this is yet a novel piece of good news in the realm of edge colouring, and should motivate for more investigations to follow. Current results: the algorithm in the paper went on Algorithmica can be further developed in order to provide, for any fixed B, a polynomial time algorithm for the computation of the excessive (B)-factorization index and of the excessive [B]-factorization index of any simple graph. Last year we submitted a work on this, that this summer got accepted by JGT. In the talk, I would like to expose the technical edge-coloring result went on Algorithmica and, if that will fit the time-slot, also its extension to the computation of the factorization indexes. In the talk or in discussions to follow, I would also like to share the sidepath problems we left open. David's publications list: Romeo Rizzi, David Cariolaro: Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes. Algorithmica 69(3): 494-500 (2014) David Cariolaro, Zhaiming Shen, Yi Zhang: Group Testing with Pools of Fixed Size. CoRR abs/1407.3631 (2014) David Cariolaro, Romeo Rizzi: Excessive factorizations of bipartite multigraphs. Discrete Applied Mathematics 158(16): 1760-1766 (2010) David Cariolaro, Hung-Lin Fu: Covering graphs with matchings of fixed size. Discrete Mathematics 310(2): 276-287 (2010) David Cariolaro, Hung-Lin Fu: The Excessive [3]-Index of All Graphs. Electr. J. Comb. 16(1) (2009) David Cariolaro: A theorem in edge colouring. Discrete Mathematics 309(12): 4208-4209 (2009) David Cariolaro, Hung-Lin Fu: Excessive near 1-factorizations. Discrete Mathematics 309(14): 4690-4696 (2009) David Cariolaro, Anthony J. W. Hilton: An application of Tutte's Theorem to 1-factorization of regular graphs of high degree. Discrete Mathematics 309(14): 4736-4745 (2009) David Cariolaro: An adjacency lemma for critical multigraphs. Discrete Mathematics 308(20): 4791-4795 (2008) David Cariolaro, Hung-Lin Fu: On minimum sets of 1-factors covering a complete multipartite graph. Journal of Graph Theory 58(3): 239-250 (2008) David Cariolaro: On fans in multigraphs. Journal of Graph Theory 51(4): 301-318 (2006) David Cariolaro, Gianfranco Cariolaro: Colouring the Petals of a Graph. Electr. J. Comb. 10 (2003)