Approximating Vizing's independence number conjecture

MaRDI QIDQ4616100zbMATH OpenFDO

Authors Eckhard Steffen

Publication date 30 January 2019

Full work available at URL https://arxiv.org/abs/1609.00808, http://ajc.maths.uq.edu.au/pdf/71/ajc_v71_p153.pdf

zbMATH Keywords

edge-chromatic critical graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: In 1965, Vizing conjectured that the independence ratio of edge-chromatic critical graphs is at most $frac12$. We prove that for every $epsilon>0$ this conjecture is equivalent to its restriction on a specific set of edge-chromatic critical graphs with independence ratio smaller than $frac12+epsilon$.

Recommendations

• An application of Vizing and Vizing-like adjacency lemmas to Vizing's independence number conjecture of edge chromatic critical graphs
• On the independence number of edge chromatic critical graphs.
• On the independence number of edge chromatic critical graphs
• A note on Vizing's independence number conjecture of edge chromatic critical graphs
• Bounds for the Independence Number of Critical Graphs

Cites work

• A new upper bound for the independence number of edge chromatic critical graphs
• A note on Vizing's independence number conjecture of edge chromatic critical graphs
• An application of Vizing and Vizing-like adjacency lemmas to Vizing's independence number conjecture of edge chromatic critical graphs
• Bounds for the Independence Number of Critical Graphs
• Chromatic-index-critical graphs of even order
• scientific article; zbMATH DE number 3266380 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• Independent sets and 2‐factors in edge‐chromatic‐critical graphs
• On the independence number of edge chromatic critical graphs.
• Regular n-valent n-connected non-Hamiltonian non n-edge-colourable graphs
• The independence number of an edge-chromatic critical graph

Cited in

(6)

• Graph edge coloring: a survey
• Reducing Vizing's 2-factor conjecture to Meredith extension of critical graphs
• On the independence number of edge chromatic critical graphs
• Fractional matchings, component-factors and edge-chromatic critical graphs
• Independence number of edge‐chromatic critical graphs
• Cycles in graphs with large independence ratio

This page was built for publication: Approximating Vizing's independence number conjecture

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