Colorability of glued graphs

Abstract

Let G₁ and G₂ be any two graphs. Let H₁ and H₂ be non-trivial connected subgraphs of G₁ and G₂, respectively, such that H₁ ≅ H₂ with an isomorphism ƒ, then the glued graph of G₁ and G₂ at H₁ and H₂ with respect to ƒ, denoted by G₁<>G₂ / H₁ ≅ H₂ is the graph that results from combining G₁ with G₂ by identifying H₁ and H₂ with respect to the isomorphism ƒ between H₁ and H₂. We investigate the results of the graph obtaining by gluing graphs of the same type where the types we are interested in are forests, trees, bipartite graphs, k-partite graphs, chordal graphs and interval graphs. Furthermore, we study properties of glued graphs involving in their colorability and edge-colorability. We give bounds of the chromatic numbers and the edge-chromatic numbers of glued graphs and also provide graphs to guarantee that each bound is the best possible.