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

DOI10.1002/JGT.21887zbMATH Open1339.05119OpenAlexW1751501232MaRDI QIDQ2811195FDOQ2811195

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

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
• 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

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)

Cites Work

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

Cited In (4)

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

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)