Interval edge coloring of a graph with forbidden colors

DOI10.1016/0012-365X(93)90546-6zbMath0782.05033MaRDI QIDQ1309462

Marek Kubale

Publication date: 24 February 1994

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

zbMATH Keywords

complexityboundsNP-completeinterval coloringpolynomial-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items

INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES ⋮ Preassignment requirements in chromatic scheduling ⋮ Restrictions and preassignments in preemptive open shop scheduling ⋮ Extensions of coloring models for scheduling purposes ⋮ Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors ⋮ On a multiconstrained model for chromatic scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• List-colourings of graphs
• Some results concerning the complexity of restricted colorings of graphs
• Interval vertex-coloring of a graph with forbidden colors
• A note on list-colorings
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
• The NP-Completeness of Edge-Coloring
• On Edge Coloring Bipartite Graphs
• On the Complexity of Timetable and Multicommodity Flow Problems