標題: The excessive -index of all graphs 作者: Cariolaro, DavidFu, Hung-Lin應用數學系Department of Applied Mathematics 關鍵字: excessive [m]-index;excessive [m]-factorization;matching;edge coloring 公開日期: 5-Oct-2009 摘要: Let m be a positive integer and let G be a graph. A set M of matchings of G, all of which of size m, is called an [m]-covering of G if boolean OR(M is an element of M) M = E(G). G is called [m]-coverable if it has an [m]-covering. An [m]-covering M such that vertical bar M vertical bar is minimum is called an excessive [m]-factorization of G and the number of matchings it contains is a graph parameter called excessive [m]-index and denoted by chi([m])' (G) (the value of chi([m])'(G) is conventionally set to infinity if G is not [m]-coverable). It is obvious that chi()'(G) = vertical bar E(G)vertical bar for every graph G, and it is not difficult to see that chi()'(G) = max{chi'(G), inverted right perpendicular vertical bar E(G)vertical bar/2inverted left perpendicular} for every -coverable graph G. However the task of determining chi([m])'(G) for arbitrary m and G seems to increase very rapidly in difficulty as m increases, and a general formula for m >= 3 is unknown. In this paper we determine such a formula for m = 3, there by determining the excessive -index for all graphs. URI: http://hdl.handle.net/11536/6575 ISSN: 1077-8926 期刊: ELECTRONIC JOURNAL OF COMBINATORICS Volume: 16 Issue: 1 結束頁: Appears in Collections: Articles