Inverse chromatic number problems in interval and permutation graphs

DOI10.1016/j.ejor.2014.12.028zbMath1346.05062OpenAlexW1999254574MaRDI QIDQ319198

Yerim Chung, Jean-François Culus, Marc Demange

Publication date: 6 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2014.12.028

zbMATH Keywords

graph coloringinterval graphspermutation graphsinverse combinatorial optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Inverse interval scheduling via reduction on a single machine ⋮ The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Blockers for the stability number and the chromatic number
• The edge intersection graphs of paths in a tree
• A tutorial on the use of graph coloring for some problems in robotics
• The 0-1 inverse maximum stable set problem
• Non-approximability of just-in-time scheduling
• The maximum k-colorable subgraph problem for chordal graphs
• On chain and antichain families of a partially ordered set
• On an instance of the inverse shortest paths problem
• Some partitions associated with a partially ordered set
• Extensions of coloring models for scheduling purposes
• Inverse problem of minimum cuts
• The \(k\)-track assignment problem
• The tabu search metaheuristic: How we used it
• On coloring unit disk graphs
• Scheduling equal-length jobs on identical parallel machines
• The robust coloring problem.
• The complexity analysis of the inverse center location problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On inverse traveling salesman problems
• Inverse median problems
• Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard
• On the complexity of the selective graph coloring problem in some special classes of graphs
• A survey of local search methods for graph coloring
• On some applications of the selective graph coloring problem
• Single-Machine Scheduling of Unit-Time Jobs with Earliness and Tardiness Penalties
• On the 2-Dimensional Channel Assignment Problem
• Inverse Optimization
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• The Complexity of Coloring Circular Arcs and Chords
• Inverse maximum flow and minimum cut problems
• Integer Isotone Optimization
• Frequency planning and ramifications of coloring
• Node-and edge-deletion NP-complete problems
• The structure of Sperner k-families

This page was built for publication: Inverse chromatic number problems in interval and permutation graphs