9
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Maximal \(k\)-Edge-Colorable Subgraphs, Vizing's Theorem, and Tuza's Conjecture

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We prove that if \(M\) is a maximal \(k\)-edge-colorable subgraph of a multigraph \(G\) and if \(F = \{v \in V(G) : d_M(v) \leq k-\mu(v)\}\), then \(d_F(v) \leq d_M(v)\) for all \(v \in F\). This implies Vizing's Theorem as well as a special case of Tuza's Conjecture on packing and covering of triangles. A more detailed version of our result also implies Vizing's Adjacency Lemma for simple graphs.

          Related collections

          Author and article information

          Journal
          2015-10-23
          2016-04-22
          Article
          1510.07017
          f16c85ef-47a4-4445-94dc-879949f4b570

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          05C15
          10 pages. Proved a stronger version of the main theorem implying Vizing's Adjacency Lemma, and incorporated some material from arXiv:1407.2336 to make the paper more self-contained
          math.CO

          Combinatorics
          Combinatorics

          Comments

          Comment on this article