On the computational complexity of strong edge coloring

DOI10.1016/S0166-218X(01)00237-2zbMath1016.68062WikidataQ56390686 ScholiaQ56390686MaRDI QIDQ1602692

Mohammad Mahdian

Publication date: 24 June 2002

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

zbMATH Keywords

strong edge coloringmaximum antimatching problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items

A polynomial time algorithm for strong edge coloring of partial \(k\)-trees ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ A characterization of well-indumatchable graphs having girth greater than seven ⋮ Strong edge-coloring for cubic Halin graphs ⋮ Strong edge chromatic index of the generalized Petersen graphs ⋮ The strong chromatic index of Halin graphs ⋮ Strong chromatic index of generalized Jahangir graphs and generalized Helm graphs ⋮ On the strong chromatic index of cubic Halin graphs ⋮ Unnamed Item ⋮ Local algorithms for edge colorings in UDGs ⋮ Strong edge-colouring and induced matchings ⋮ Algorithms for finding distance-edge-colorings of graphs ⋮ On the complexity of the flow coloring problem ⋮ Maximum cardinality neighbourly sets in quadrilateral free graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Unnamed Item ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ On the approximability of the maximum induced matching problem ⋮ Strong edge-coloring for jellyfish graphs ⋮ Proof of a conjecture on the strong chromatic index of Halin graphs ⋮ Acyclic, star, and injective colouring: bounding the diameter ⋮ Recent progress on strong edge-coloring of graphs ⋮ From edge-coloring to strong edge-coloring ⋮ Strong edge coloring of Cayley graphs and some product graphs ⋮ Injective colouring for H-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Induced matchings in bipartite graphs
• Induced matchings
• New results on induced matchings
• The strong chromatic index ofC4-free graphs
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem