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

DOI10.1016/J.DISC.2017.02.020MaRDI QIDQ526243zbMATHOpenAlexWikidataFDO

Authors Gregory J. Puleo

Publication date 10 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(11)

• The maximal clique and colourability of curve contact graphs
• Triangle packing and covering in dense random graphs
• Graph edge coloring: a survey
• Maximum \(\Delta \)-edge-colorable subgraphs of class II graphs
• A new tool for proving Vizing's theorem
• Graphs with \(\alpha _1\) and \(\tau _1\) both large
• scientific article; zbMATH DE number 3861194 (Why is no real title available?)
• Kőnig's line coloring and Vizing's theorems for graphings
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• Maximal edge-colorings of graphs
• Maximal ambiguously \(k\)-colorable graphs

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)