Measurements of edge-uncolorability. (English) Zbl 1041.05031

Summary: 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 \(c_k\) be the maximum size of a \(k\)-colorable subgraph of a cubic graph \(G=(V,E)\). We consider \(r_3=|E|-c_3\) and \(r_2=\frac{2}{3}|E|-c_2\). We show that on one side \(r_3\) and \(r_2\) bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness \(\omega\) of \(G\), the smallest possible number of odd circuits in a 2-factor of \(G\). We construct cyclically 5-edge connected cubic graphs where \(r_3\) and \(\omega\) are arbitrarily far apart, and show that for each \(1 \leqslant c < 2\) there is a cubic graph such that \(\omega \geqslant cr_3\). For \(k=2,3\), let \(\zeta_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.


05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Albertson, M.O.; Haas, R., Parsimonious edge coloring, Discrete math., 148, 1-7, (1996) · Zbl 0845.05036
[2] Albertson, M.O.; Haas, R., The edge chromatic difference sequence of a cubic graph, Discrete math., 177, 1-8, (1997) · Zbl 0894.05018
[3] Brinkmann, G.; Steffen, E., Snarks and reducibility, Ars combin., 50, 292-296, (1998) · Zbl 0963.05050
[4] S. Fiorini, Hypohamiltonian snarks, in: Graphs and other combinatorial topics, Teubner, Leipzig, 1983, pp. 70-75.
[5] Huck, A.; Kochol, M., Five cycle double covers of some cubic graphs, J. combin. theory ser. B, 64, 116-125, (1995) · Zbl 0820.05045
[6] Isaacs, R., Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. math. monthly, 82, 221-239, (1975) · Zbl 0311.05109
[7] Johnson, E.L., A proof of 4-coloring the edges of a cubic graph, Amer. math. monthly, 73, 52-55, (1966) · Zbl 0131.20805
[8] Kochol, M., Snarks without small cycles, J. combin. theory ser. B, 67, 34-47, (1996) · Zbl 0855.05066
[9] Steffen, E., Classifications and characterizations of snarks, Discrete math., 188, 183-203, (1998) · Zbl 0956.05089
[10] H.P. Yap, Some topics in graph theory, London Math. LNS 108, Cambridge University Press, Cambridge, NY, 1986. · Zbl 0588.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.