An H-immersion is a model of a graph H in a larger graph G. Vertices of H are representedby distinct "branch" vertices in G, while edges of H are represented by edge-disjoint walksin G joining branch vertices. By the recently proved Nash-Williams Immersion Conjecture,any immersion-closed family is characterized by forbidding the presence of H-immersions forafinite number of graphs H. We off er descriptions of some immersion-closed families alongwith their forbidden immersion characterizations. Our principal results in this area are acharacterization of graphs with no K_{2,3}-immersion, and a characterization of graphs withneither a K_{2,3}-immersion nor a K_4-immersion. We study of the maximum number of edgesin an n-vertex graph with no K_t-immersion. For t≤7, we determine this maximum value.When 5≤t≤7, we characterize the graphs with no K_t-immersion having the most edges.Given an edge-colored graph, a rainbow subgraph is a subgraph whose edges have distinctcolors. We show that if the edges of a graph G are colored so that at least k colors appearat each vertex, then G contains a rainbow matching of size floor(k/2). We consider the rainbowedge-chromatic number of an edge-colored graph,\chi'_r(G), which we define to be the minimumnumber of rainbow matchings partitioning the edge set of G. A d-tolerant edge-coloredgraph is one that contains no monochromatic star with d + 1 edges. We off er examplesof d-tolerant n-vertex edge-colored graphs G for which\chi'_r(G)≥d/2 (n-1) and prove that \chi'_r(G)
PDF
download
878987797
028-85220240
