Randomized online graph coloring

DOI10.1016/0196-6774(92)90061-GMaRDI QIDQ4015271zbMATH OpenOpenAlexFDO

Authors Sundar Vishwanathan

Publication date 12 January 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(92)90061-g

zbMATH Keywords

chromatic numberlower boundonline graph coloring algorithmpolynomial timerandomized online algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Online graph coloring against a randomized adversary
• Coloring random graphs online without creating monochromatic subgraphs
• Coloring random graphs online without creating monochromatic subgraphs
• Online coloring of hypergraphs
• On-line list colouring of random graphs
• Online vertex-coloring games in random graphs
• Online hypergraph coloring
• On-Line Coloring and Recursive Graph Theory
• scientific article; zbMATH DE number 1303205
• On-line coloring \(k\)-colorable graphs

Cited in

(31)

• An on-line graph coloring algorithm with sublinear performance ratio
• On-line coloring \(k\)-colorable graphs
• Coloring inductive graphs on-line
• Lower bounds for on-line graph coloring
• On-line coloring of perfect graphs
• On-line edge-coloring with a fixed number of colors
• On the on-line chromatic number of the family of on-line 3-chromatic graphs
• Online coloring known graphs
• Tight bounds for online coloring of basic graph classes
• Online coloring co-interval graphs
• On-Line Coloring of Sparse Random Graphs and Random Trees
• Online graph coloring against a randomized adversary
• The graph-bin packing problem
• Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing
• Impartial coloring games
• scientific article; zbMATH DE number 1303205 (Why is no real title available?)
• Parallel and On-Line Graph Coloring
• scientific article; zbMATH DE number 742967 (Why is no real title available?)
• Online coloring of bipartite graphs with and without advice
• On-line list colouring of random graphs
• Tight bounds for online coloring of basic graph classes
• Online vertex-coloring games in random graphs
• Online hypergraph coloring with rejection
• Dynamic graph coloring
• Online coloring and a new type of adversary for online graph problems
• Online edge coloring via tree recurrences and correlation decay
• Online coloring of hypergraphs
• First-fit coloring of forests in random arrival model
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Online coloring graphs with high girth and high odd girth
• Online hypergraph coloring

This page was built for publication: Randomized online graph coloring

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