Induced Decompositions of Highly Dense Graphs |
| |
| Authors: | Nathann Cohen Zsolt Tuza |
| |
| Institution: | 1. LABORATOIRE DE RECHERCHE EN INFORMATIQUE – UNIVERSITé PARIS‐SUD 11 – RUE NOETZLIN, GIF‐SUR‐YVETTE, FRANCE;2. DEPARTMENT OF COMPUTER SCIENCE AND SYSTEMS TECHNOLOGY, UNIVERSITY OF PANNONIA, VESZPRéM, HUNGARY;3. ALFRéD RéNYI INSTITUTE OF MATHEMATICS, HUNGARIAN ACADEMY OF SCIENCES, BUDAPEST, HUNGARY |
| |
| Abstract: | Given two graphs F and G, an induced F‐decomposition of G is a partition of  into induced subgraphs isomorphic to F. Bondy and Szwarcfiter J. Graph Theory, DOI: 10.1002/jgt.21654] defined the value  as the maximum number of edges in a graph of order n admitting an induced F‐decomposition and determined the value of  for some graphs (and families of graphs). In this article, we prove that  is valid for all graphs F. We also present tighter asymptotic bounds for some of the small graphs for which the exact value of  remains unknown. The proofs are based on the heavy use of various classes of Kneser graphs and hypergraphs. |
| |
| Keywords: | induced decompositions hypergraphs |
|
|
