Measurements of edge-uncolorability |
| |
Authors: | Eckhard Steffen |
| |
Institution: | International Graduate School Dynamic Intelligent Systems, Universität Paderborn, Warburger Str. 100, 33098 Paderborn, Germany |
| |
Abstract: | Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let ck be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r3=|E|?c3 and
. We show that on one side r3 and r2 bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r3 and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr3. For k=2,3, let ζk denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other. |
| |
Keywords: | Author Keywords: Chromatic index Cubic graphs Snarks Edge chromatic difference sequence |
本文献已被 ScienceDirect 等数据库收录! |
|