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

DOI10.1016/J.DISOPT.2011.04.004zbMATH Open1242.05085OpenAlexW2164841845MaRDI QIDQ666002FDOQ666002

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

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

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)

Cites Work

• On the deficiency of bipartite graphs
• Chromatic scheduling in a cyclic open shop
• Compact cyclic edge-colorings of graphs
• The deficiency of a regular graph
• On interval colourings of bi-regular bipartite graphs
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• Title not available (Why is that?)
• Interval colorings of edges of a multigraph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Consecutive colorings of the edges of general graphs
• On interval edge colorings of \((\alpha ,\beta )\)-biregular bipartite graphs
• Compact Scheduling In Open Shop With Zero-One Time Operations
• Lower bounds and a tabu search algorithm for the minimum deficiency problem

Cited In (3)

• A note on compact and compact circular edge-colorings of graphs
• Compact cyclic edge-colorings of graphs
• Title not available (Why is that?)

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)