A constructive proof of Vizing's theorem
From MaRDI portal
Publication:1186590
DOI10.1016/0020-0190(92)90041-SzbMath0795.68157WikidataQ29302123 ScholiaQ29302123MaRDI QIDQ1186590
Publication date: 28 June 1992
Published in: Information Processing Letters (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Coloring of graphs and hypergraphs (05C15)
Related Items
MPI+X: task-based parallelisation and dynamic load balance of finite element assembly ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Edge coloring: a natural model for sports scheduling ⋮ A new neighborhood structure for round robin scheduling problems ⋮ On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions ⋮ Chromatic index of dense quasirandom graphs ⋮ An exact algorithm for the edge coloring by total labeling problem ⋮ On Vizing's edge colouring question ⋮ Edge coloring graphs with large minimum degree ⋮ An alternating direction method of multipliers for solving user equilibrium problem ⋮ Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Decompositions for the edge colouring of reduced indifference graphs. ⋮ The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size ⋮ Tight bound for matching ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ Link scheduling in wireless sensor networks: distributed edge-coloring revisited ⋮ Local algorithms for edge colorings in UDGs ⋮ Assigning times to minimise reachability in temporal graphs ⋮ Optimal path and cycle decompositions of dense quasirandom graphs ⋮ Random perfect graphs ⋮ Quantum Monte Carlo annealing with multi-spin dynamics ⋮ Towards the linear arboricity conjecture ⋮ A new multi-resolution parallel framework for SPH ⋮ Very fast parallel algorithms for approximate edge coloring ⋮ Approximating the maximum 2- and 3-edge-colorable subgraph problems ⋮ Decompositions for edge-coloring join graphs and cobipartite graphs ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions ⋮ Incidence coloring of mycielskians with fast algorithm ⋮ Approximating the maximum 3-edge-colorable subgraph problem ⋮ On the hardness of determining the irregularity strength of graphs ⋮ Distributed link scheduling in wireless networks
Cites Work
