On the complexity of computing the excessive [B]-index of a graph

DOI10.1002/JGT.21887MaRDI QIDQ2811195zbMATHOpenAlexFDO

Authors Romeo Rizzi, D. Cariolaro

Publication date 10 June 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.21887

zbMATH Keywords

matchingchromatic indexexcessive \([B\)-factorization]excessive \([B\)-index]

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Algorithms and complexity results for finding graphs with extremal Randić index
• A complexity problem for Borel graphs
• The complexity of determining the vertex-rainbow index of graphs
• On a certain complexity estimate in graph theory
• An upper bound for the excessive index of an \(r\)-graph
• On the complexity of some problems related to graph extensions
• scientific article; zbMATH DE number 3876594
• On the complexity of determining the irregular chromatic index of a graph
• A complexity dichotomy for critical values of the b-chromatic number of graphs
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs

Cites work

• scientific article; zbMATH DE number 3378938 (Why is no real title available?)
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• An upper bound for the excessive index of an \(r\)-graph
• Bipartite Edge Coloring in $O(\Delta m)$ Time
• Covering graphs with matchings of fixed size
• Excessive factorizations of bipartite multigraphs
• Excessive near 1-factorizations
• Graphs of arbitrary excessive class
• On excessive index of certain networks
• On minimum sets of 1-factors covering a complete multipartite graph
• On the excessive \([m]\)-index of a tree
• Paths, Trees, and Flowers
• Polynomial time complexity of edge colouring graphs with bounded colour classes
• Research problems from the BCC21
• The NP-Completeness of Edge-Coloring
• The Solution of a Timetabling Problem
• The equivalence of two conjectures of Berge and Fulkerson
• The excessive [3]-index of all graphs

Cited in

(4)

• Excessive \([l, m]\)-factorizations
• On the excessive \([m]\)-index of a tree
• On excessive index of certain networks
• Excessive factorizations of bipartite multigraphs

This page was built for publication: On the complexity of computing the excessive \([B]\)-index of a graph

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