Online Bounded Coloring of Permutation and Overlap Graphs

DOI10.1016/J.ENDM.2008.01.037MaRDI QIDQ3503553zbMATH OpenOpenAlexFDO

Authors Marc Demange, Gabriele Di Stefano, Benjamin Leroy-Beaulieu

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2008.01.037

zbMATH Keywords

bounded coloringcompetitive analysisFirst-Fitonline algorithmsoverlap graphspermutation graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27)

Recommendations

• Generalised online colouring problems in overlap graphs
• A note on online colouring problems in overlap graphs and their complements
• Tight bounds for online coloring of basic graph classes
• Tight bounds for online coloring of basic graph classes
• On-line P-coloring of graphs
• On-line coloring of perfect graphs
• Online coloring of hypergraphs
• Lower bounds for on-line graph colorings
• Online Conflict-Free Colorings for Hypergraphs
• scientific article; zbMATH DE number 742967

Cites work

• A graph theoretical approach to the shunting problem
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• On the performance of the first-fit coloring algorithm on permutation graphs
• Track assignment

Cited in

(3)

• A note on online colouring problems in overlap graphs and their complements
• Generalised online colouring problems in overlap graphs
• On inverse chromatic number problems (extended abstract)

This page was built for publication: Online Bounded Coloring of Permutation and Overlap Graphs

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