Maximal k-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture

DOI10.1016/J.DISC.2017.02.020zbMATH Open1361.05053arXiv1510.07017OpenAlexW2107648567WikidataQ123136090 ScholiaQ123136090MaRDI QIDQ526243FDOQ526243

Gregory J. Puleo

Publication date: 10 May 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove that if $M$ is a maximal $k$-edge-colorable subgraph of a multigraph $G$ and if $F=vinV(G):d_M(v)leqk-mu(v)$, then $d_F(v)leq{d}_M(v)$ for all $vinF$. (When $G$ is a simple graph, the set $F$ is just the set of vertices having degree less than $k$ in $M$.) 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.

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

Recommendations

• A generalization of edge-coloring in graphs
• Proof of Melnikov-Vizing conjecture for multigraphs with maximum degree at most \(3\)
• An extension of Vizing's theorem
• On Vizing's theorem, adjacency lemma and fan argument generalized to multigraphs
• On characterizing Vizing's edge colouring bound

zbMATH Keywords

edge coloringTuza's conjectureVizing's theorem\(k\)-dependent set\(k\)-edge-colorable subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• Matching theory
• Title not available (Why is that?)
• \(k\)-domination and \(k\)-independence in graphs: A survey
• Title not available (Why is that?)
• Approximating the maximum 3-edge-colorable subgraph problem
• On a conjecture of Tuza about packing and covering of triangles
• Small edge sets meeting all triangles of a graph
• A conjecture on triangles of graphs
• Tuza's conjecture for graphs with maximum average degree less than 7
• Title not available (Why is that?)
• Title not available (Why is that?)
• On edge-colorings of graphs.
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Subgraphs with prescribed valencies
• Title not available (Why is that?)
• Packing and covering triangles in graphs
• A stability theorem on fractional covering of triangles by edges
• Integer and fractional packings in dense graphs
• An application of matching theory of edge-colourings
• Packing and covering triangles in \(K_{4}\)-free planar graphs
• On disjoint matchings in cubic graphs: maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs
• A new tool for proving Vizing's theorem
• Maximum \(\Delta \)-edge-colorable subgraphs of class II graphs
• A short proof for a generalization of Vizing's theorem
• Packing Triangles in Weighted Graphs
• Approximating maximum edge 2-coloring in simple graphs

Cited In (8)

• Triangle packing and covering in dense random graphs
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• The maximal clique and colourability of curve contact graphs
• Maximum \(\Delta \)-edge-colorable subgraphs of class II graphs
• Maximal ambiguously \(k\)-colorable graphs
• Graphs with \(\alpha _1\) and \(\tau _1\) both large
• Graph edge coloring: a survey
• Title not available (Why is that?)

This page was built for publication: Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526243)