Chromatically Supremal Decompositions of Graphs
Tóm tắt
If G is a graph, a G-decomposition of a host graph H is a partition of the edges of H into subgraphs of H which are isomorphic to G. The chromatic index of a G-decomposition of H is the minimum number of colors required to color the parts of the decomposition so that parts which share a common node get different colors. We establish an upper bound on the chromatic index and characterize those decompositions which achieve it. The structurally most interesting of the decompositions with maximal chromatic index are associated with (v, k, 1)-designs.
Tài liệu tham khảo
Assmus E.F., Key J.D.: Designs and Their Codes, pp. 7. Cambridge University Press, New York (1992)
Brooks R.L.: On colouring the nodes of a network. Proc. Camb. Phil. Soc. 37, 194–197 (1941)
Danziger P., Graham A., Mendelsohn E.: The chromatic spectrum of graph designs. Bull. Inst. Combin. Appl. 50, 71–96 (2007)
Dembowski P.: Finite Geometries, pp. 4–5. Springer-Verlag, New York (1968)
Gropp H.: Configurations. In: Colbourn, C.J., Dinitz, J.H. (eds) The CRC Handbook of Combinatorial Designs., pp. 253–255. CRC Press, Boca Raton (1996)
Harary F., Robinson R.W., Wormald N.C.: Isomorphic factorisations I. Complete graphs. Trans. Am. Math. Soc. 242, 243–260 (1978)
Jamison R.E., Mendelsohn E.: On the chromatic spectrum of acyclic decompositions of graphs. J. Graph Theory 56, 83–104 (2007)
Jamison R.E., White J.H.: On intersection graphs of 2-matchings in cubic graphs. Congr. Numerantium 181, 187–193 (2006)
West D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall Inc., Upper Saddle River (2001)