On compact k-edge-colorings: a polynomial time reduction from linear to cyclic

DOI10.1016/J.DISOPT.2011.04.004MaRDI QIDQ666002zbMATH OpenOpenAlexFDO

Authors Sivan Altinakar, Gilles Caporossi, Alain Hertz

Publication date 7 March 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2011.04.004

zbMATH Keywords

consecutive edge-coloringscyclic edge-coloringsinterval edge-colorings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Compact cyclic edge-colorings of graphs
• Polynomial time complexity of edge colouring graphs with bounded colour classes
• A note on compact and compact circular edge-colorings of graphs
• A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs
• Linear algebraic approach to an edge-coloring result
• On the algorithmic complexity of zero-sum edge-coloring
• Simple reduction of f-colorings to edge-colorings
• A polyhedral approach to edge coloring
• Linear-time algorithm for the edge-colorability of a graph with prescribed vertex types
• From edge colorings to graph decompositions -- results and problems

Cites work

• scientific article; zbMATH DE number 165470 (Why is no real title available?)
• scientific article; zbMATH DE number 951847 (Why is no real title available?)
• scientific article; zbMATH DE number 1409249 (Why is no real title available?)
• Chromatic scheduling in a cyclic open shop
• Compact Scheduling In Open Shop With Zero-One Time Operations
• Compact cyclic edge-colorings of graphs
• Consecutive colorings of the edges of general graphs
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• Interval colorings of edges of a multigraph
• Lower bounds and a tabu search algorithm for the minimum deficiency problem
• On interval colourings of bi-regular bipartite graphs
• On interval edge colorings of ( , )-biregular bipartite graphs
• On the deficiency of bipartite graphs
• The deficiency of a regular graph

Cited in

(3)

• A note on compact and compact circular edge-colorings of graphs
• Compact cyclic edge-colorings of graphs
• scientific article; zbMATH DE number 7141490 (Why is no real title available?)

This page was built for publication: On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic

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