Colorful edge decomposition of graphs: some polynomial cases

DOI10.1016/J.DAM.2016.10.019MaRDI QIDQ2403802zbMATH OpenOpenAlexFDO

Authors A. Dehghan, Mohammad-Reza Sadeghi

Publication date 12 September 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.10.019

zbMATH Keywords

graph decompositionpolynomial algorithmtotally unimodular matrixcolorful edge decompositionpalette

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Edge \(k\)-\(q\)-colorability of graphs
• Edge Coloring and Decompositions of Weighted Graphs
• On sum edge-coloring of regular, bipartite and split graphs
• Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings
• Rainbow graph splitting

Cites work

• scientific article; zbMATH DE number 4094812 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• Algorithmic complexity of proper labeling problems
• Decomposition of balanced complete bipartite multigraphs into multistars
• Decompositions for edge-coloring join graphs and cobipartite graphs
• Edge decompositions into two kinds of graphs
• Edge decompositions of multigraphs into 3-matchings
• Factors and factorizations of graphs. Proof techniques in factor theory
• Minimum number of palettes in edge colorings
• Multigraph decomposition into stars and into multistars
• NP completeness of finding the chromatic index of regular graphs
• On the complexity of deciding whether the regular number is at most two
• On the complexity of determining the irregular chromatic index of a graph
• On the complexity of the colorful directed paths in vertex coloring of digraphs
• Palettes in block colourings of designs
• Paths, Trees, and Flowers
• Regular factors of regular graphs
• The NP-Completeness of Some Edge-Partition Problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Vertex colouring edge partitions

This page was built for publication: Colorful edge decomposition of graphs: some polynomial cases

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