Randomized online graph coloring
DOI10.1016/0196-6774(92)90061-GzbMATH Open0768.68185OpenAlexW2084263468MaRDI QIDQ4015271FDOQ4015271
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
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
chromatic numberlower boundpolynomial timerandomized online algorithmonline graph coloring algorithm
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cited In (28)
- Online edge coloring via tree recurrences and correlation decay
- On the on-line chromatic number of the family of on-line 3-chromatic graphs
- Online coloring known graphs
- Online coloring of bipartite graphs with and without advice
- An on-line graph coloring algorithm with sublinear performance ratio
- Online coloring graphs with high girth and high odd girth
- Tight Bounds for Online Coloring of Basic Graph Classes
- Lower bounds for on-line graph coloring
- Adding isolated vertices makes some greedy online algorithms optimal
- On-line coloring of perfect graphs
- Dynamic graph coloring
- On-line coloring \(k\)-colorable graphs
- Coloring inductive graphs on-line
- Online vertex-coloring games in random graphs
- Title not available (Why is that?)
- Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
- Online Graph Coloring Against a Randomized Adversary
- Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing
- Tight bounds for online coloring of basic graph classes
- The graph-bin packing problem
- Online hypergraph coloring with rejection
- Online hypergraph coloring
- Title not available (Why is that?)
- On-line edge-coloring with a fixed number of colors
- Online coloring of hypergraphs
- Impartial coloring games
- Online coloring and a new type of adversary for online graph problems
- Online coloring co-interval graphs
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)
