First-fit coloring of bounded tolerance graphs

DOI10.1016/j.dam.2010.05.002zbMath1210.05043OpenAlexW2074455464MaRDI QIDQ531602

Karin R. Saoub, Henry A. Kierstead

Publication date: 19 April 2011

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

Full work available at URL: https://doi.org/10.1016/j.dam.2010.05.002

zbMATH Keywords

Grundy numbertolerance graphfirst-fit

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

Grundy Distinguishes Treewidth from Pathwidth ⋮ Unnamed Item ⋮ Computational aspects of greedy partitioning of graphs ⋮ Complexity of Grundy coloring and its variants ⋮ First-fit coloring of bounded tolerance graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-fit coloring on interval graphs has performance ratio at least 5
• First-fit coloring of bounded tolerance graphs
• Tolerance graphs
• A note on first-fit coloring of interval graphs
• Induced subtrees in graphs of large chromatic number
• A polynomial time approximation algorithm for dynamic storage allocation
• Coloring interval graphs with First-Fit
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• The Linearity of First-Fit Coloring of Interval Graphs
• On some packing problem related to dynamic storage allocation
• An Effective Version of Dilworth's Theorem
• Tolerance graphs, and orders
• Radius two trees specify χ‐bounded classes
• On-Line Coloring and Recursive Graph Theory
• OPTVersusLOADin Dynamic Storage Allocation

This page was built for publication: First-fit coloring of bounded tolerance graphs