Bounded vertex colorings of graphs

DOI10.1016/0012-365X(93)90165-PzbMath0782.05032OpenAlexW2052136967MaRDI QIDQ686481

Julio Kuplinsky, Alain Hertz, Pierre Hansen

Publication date: 20 December 1993

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

Full work available at URL: https://doi.org/10.1016/0012-365x(93)90165-p

zbMATH Keywords

complexityboundschromatic numberbounded chromatic numbermaximum degreebounded vertex coloring

Mathematics Subject Classification ID

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

Related Items (25)

Scheduling with conflicts: Online and offline algorithms ⋮ Coloration de graphes : fondements et applications ⋮ Restricted coloring models for timetabling ⋮ What are the worst cases in constrained last-in-first-out pick-up and delivery problems? ⋮ On equitable chromatic number of Tadpole graph T_{m,n} ⋮ The prisoner transportation problem ⋮ Equitable coloring of hypergraphs ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ The mutual exclusion scheduling problem for permutation and comparability graphs. ⋮ Scheduling with machine conflicts ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Partitioning a weighted partial order ⋮ A survey on vertex coloring problems ⋮ A tutorial on the use of graph coloring for some problems in robotics ⋮ Bounded colouring motivated by the limited resource partially concurrent open shop problem ⋮ Batch processing with interval graph compatibilities between tasks ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Heuristics and lower bounds for the bin packing problem with conflicts ⋮ Partitioning graphs into induced subgraphs ⋮ Locally boundedk-colorings of trees ⋮ Graph coloring with cardinality constraints on the neighborhoods ⋮ Clique partitioning with value-monotone submodular cost ⋮ An overview of curriculum-based course timetabling ⋮ Equitable colorings of bounded treewidth graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• Chromatic optimisation: Limitations, objectives, uses, references
• Critical perfect graphs and perfect 3-chromatic graphs
• Normal hypergraphs and the perfect graph conjecture
• On Complementary Graphs
• Two-Processor Scheduling with Start-Times and Deadlines
• On the completeness of a generalized matching problem

This page was built for publication: Bounded vertex colorings of graphs