Tomoki Nakamigawa - Equivalent Subgraphs of Order $3$

dmtcs:3460 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3460
Equivalent Subgraphs of Order $3$Conference paper

Authors: Tomoki Nakamigawa 1

  • 1 Department of Information Science


It is proved that any graph of order $14n/3 + O(1)$ contains a family of n induced subgraphs of order $3$ such that they are vertex-disjoint and equivalent to each other.

https://doi.org/10.46298/dmtcs.3460
Source: HAL:hal-01184449v1
Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] graph Ramsey theory, graph decomposition

Share and export

Consultation statistics

This page has been seen 270 times.
This article's PDF has been downloaded 273 times.