On the Complexity of Computing the Excessive [B]-Index of a Graph

DOI10.1002/jgt.21887zbMath1339.05119OpenAlexW1751501232MaRDI QIDQ2811195

Romeo Rizzi, David 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

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

Cites Work

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