Maximum Δ-edge-colorable subgraphs of class II graphs

DOI10.1002/jgt.20629zbMath1247.05084arXiv1002.0783OpenAlexW1564268779MaRDI QIDQ2911495

Eckhard Steffen, Vahan V. Mkrtchyan

Publication date: 31 August 2012

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1002.0783

zbMATH Keywords

matching2-factorchromatic indexedge-chromatic numberclass II graphmaximum \(\Delta \)-edge-colorable subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (7)

Three measures of edge-uncolorability ⋮ Decomposition of class II graphs into two class I graphs ⋮ Measures of edge-uncolorability ⋮ On maximum \(k\)-edge-colorable subgraphs of bipartite graphs ⋮ Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture ⋮ Parsimonious edge-coloring on surfaces ⋮ Minimal edge colorings of class 2 graphs and double graphs

Cites Work

• On the chromatic index of multigraphs without large triangles
• On disjoint matchings in cubic graphs
• Approximating the maximum 3-edge-colorable subgraph problem
• Classification and characterizations of snarks
• Parsimonious edge coloring
• A refinement of Vizing's theorem

This page was built for publication: Maximum Δ-edge-colorable subgraphs of class II graphs