2011-06-19T16:00:00 2011-06-25T16:00:00 2010-08-16T15:35:50 2013-05-25T06:16:49 Europe/Ljubljana Prof. Prof. Prof. Prof. 11 false [["minutes", "Minutes"], ["paper", "Paper"], ["poster", "Poster"], ["slides", "Slides"]] Coloring of Graphs 0 Oral presentation Maximum $Delta$-edge-colorable subgraphs of class II graphs Paderborn University es@upb.de Paderborn University es@upb.de Yerevan State University vahanmkrtchyan2002@gmail.com Bled, Slovenia
A graph is class II, if its chromatic index is at least $\Delta+1$. There are long standing open conjectures on class II graphs, and it is a notorious difficult open problem to characterize class II graphs or even to obtain some insight into their structural properties. In the first part we study parameters that give us some information about how far the graph is from being class 1, and we relate these parameters to each other. For instance, let $r(G)$ be the minimum number of edges that have to be removed from a multigraph $G$ to obtain a $\Delta(G)$-edge-colorable subgraph, and let $r_v(G)$ be the minimum number of vertices that have to be removed from $G$ to obtain a class 1 graph. We show that $\frac{r(G)}{r_v(G)} \leq \lfloor \frac{\Delta(G)}{2} \rfloor$, and that this bound is best possible. The second part of the talk focuses on the $\Delta$-edge-colorable part of graphs. Let $H$ be a maximum $\Delta$-edge-colorable subgraph of $G$. We prove best possible lower bounds for $\frac{|E(H)|}{|E(G)|}$, and study structural properties of maximum $\Delta$-edge-colorable subgraphs. We show that every set of vertex-disjoint cycles of a class II graph with $\Delta\geq3$ can be extended to a maximum $\Delta$-edge-colorable subgraph. Simple graphs have a maximum$\Delta$-edge-colorable subgraph such that the complement is a matching. Furthermore, a maximum $\Delta$-edge-colorable subgraph of a simple graph is always class I