Edge-Chromatic Numbers of Glued Graphs

C. Promsakon, C. Uiyyasathian

Abstract

Let $G_1$ and $G_2$ be any two graphs. Assume that $H_1\subseteq G_1$ and $H_2\subseteq G_2$ are connected, not a single vertex and such that $H_1 \cong H_2$ with an isomorphism f. The glued graph of $G_1$ and $G_2$ at $H_1$ and $H_2$ with respect to f, denoted by, is the graph that results from combining $G_1$ with $G_2$ by identifying $H_1$ and $H_2$ with respect to the isomorphism f between $H_1$ and $H_2$. We give upper bounds of the edge-chromatic numbers of glued graphs; one is in terms of the edge-chromatic numbers of their original graphs where we give a characterization of graphs satisfying its equality. We further obtain a better upper bound of the chromatic numbers of glued graphs when the original graphs are line graphs.