Colorful edge decomposition of graphs: some polynomial cases

DOI10.1016/J.DAM.2016.10.019zbMATH Open1369.05179OpenAlexW2557089399MaRDI QIDQ2403802FDOQ2403802

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

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

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)

Cites Work

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

Cited In (1)

• Decomposing edge-colored graphs under color degree constraints

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)