On subgraphs induced by transversals in vertex-partitions of graphs
The electronic journal of combinatorics, Tome 13 (2006)
For a fixed graph $H$ on $k$ vertices, we investigate the graphs, $G$, such that for any partition of the vertices of $G$ into $k$ color classes, there is a transversal of that partition inducing $H$. For every integer $k\geq 1$, we find a family ${\cal F}$ of at most six graphs on $k$ vertices such that the following holds. If $H\notin {\cal F}$, then for any graph $G$ on at least $4k-1$ vertices, there is a $k$-coloring of vertices of $G$ avoiding totally multicolored induced subgraphs isomorphic to $H$. Thus, we provide a vertex-induced anti-Ramsey result, extending the induced-vertex-Ramsey theorems by Deuber, Rödl et al.
DOI :
10.37236/1062
Classification :
05C15
Mots-clés : anti-Ramsey result, induced-vertex-Ramsey theorems
Mots-clés : anti-Ramsey result, induced-vertex-Ramsey theorems
@article{10_37236_1062,
author = {Maria Axenovich},
title = {On subgraphs induced by transversals in vertex-partitions of graphs},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1062},
zbl = {1097.05018},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1062/}
}
Maria Axenovich. On subgraphs induced by transversals in vertex-partitions of graphs. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1062
Cité par Sources :