On the algorithmic complexity of zero-sum edge-coloring

DOI10.1016/J.IPL.2016.06.010MaRDI QIDQ2630333zbMATH OpenOpenAlexFDO

Authors A. Dehghan, Mohammad-Reza Sadeghi

Publication date 27 July 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2016.06.010

zbMATH Keywords

computational complexityzero-sum edge-coloringzero-sum flowzero-sum vertex flow

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of the zero-sum 3-flows
• On zero-sum 6-flows of graphs
• Problems in Zero-Sum Combinatorics
• Zero-sum flows in regular graphs
• A note on zero-sum 5-flows in regular graphs

Cites work

• A characterization of graphs with rank 5
• A dynamic survey of graph labeling
• Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Magic Graphs
• Magic square spectra
• NP completeness of finding the chromatic index of regular graphs
• On linear systems with integral valued solutions
• On the complexity of deciding whether the regular number is at most two
• On the kernels of the incidence matrices of graphs
• On the null-spaces of acyclic and unicyclic singular graphs
• On the nullity of bipartite graphs
• On zero-sum 6-flows of graphs
• Rees algebras of edge ideals
• Sequence variations of the 1-2-3 conjecture and irregularity strength
• Some classes of integral matrices
• The complexity of the zero-sum 3-flows
• The NP-Completeness of Edge-Coloring
• Zero-sum flow numbers of regular graphs

Cited in

(5)

• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• Problems in Zero-Sum Combinatorics
• The complexity of the zero-sum 3-flows
• scientific article; zbMATH DE number 6423647 (Why is no real title available?)
• On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic

This page was built for publication: On the algorithmic complexity of zero-sum edge-coloring

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