19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Maximum $Delta$-edge-colorable subgraphs of class II graphs

Presented by Eckhard STEFFEN
Type: Oral presentation
Track: Coloring of Graphs


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


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors