Inverse chromatic number problems in interval and permutation graphs

DOI10.1016/J.EJOR.2014.12.028MaRDI QIDQ319198zbMATH OpenOpenAlexFDO

Authors 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 graphsinverse combinatorial optimizationpermutation graphs

Mathematics Subject Classification ID

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

Recommendations

• On inverse chromatic number problems (extended abstract)
• Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
• scientific article; zbMATH DE number 3875312
• Inverting the Turán problem with chromatic number
• scientific article; zbMATH DE number 4057534
• The chromatic number of some permutation graphs over some graphs
• On the interval chromatic number of proper interval graphs
• scientific article; zbMATH DE number 3914342
• Colorability of mixed hypergraphs and their chromatic inversions
• scientific article; zbMATH DE number 3308988

Cites work

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

Cited in

(4)

• On inverse chromatic number problems (extended abstract)
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
• Inverse interval scheduling via reduction on a single machine

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

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