Bounded families for the on-line t-relaxed coloring

DOI10.1016/J.IPL.2005.07.001MaRDI QIDQ1044722zbMATH OpenOpenAlexFDO

Authors Agostino Capponi, Concetta Pilotto

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.07.001

zbMATH Keywords

combinatorial problemscompetitive algorithmson-line coloringrelaxed coloring

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Online algorithms; streaming algorithms (68W27)

Recommendations

• scientific article; zbMATH DE number 4170931
• On-Line Coloring and Recursive Graph Theory
• Tight bounds for online coloring of basic graph classes
• Lower bounds for on-line graph coloring
• On-Line Coloring of H-Free Bipartite Graphs

Cites work

• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• scientific article; zbMATH DE number 4134069 (Why is no real title available?)
• scientific article; zbMATH DE number 3979083 (Why is no real title available?)
• scientific article; zbMATH DE number 4008419 (Why is no real title available?)
• scientific article; zbMATH DE number 139777 (Why is no real title available?)
• scientific article; zbMATH DE number 398953 (Why is no real title available?)
• On-line and first fit colorings of graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Relaxed chromatic numbers of graphs
• Relaxed game chromatic number of graphs
• The greedy algorithm is optimal for on-line edge coloring
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(1)

• Online dominating set and coloring

This page was built for publication: Bounded families for the on-line \(t\)-relaxed coloring

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