Concepedia

Online Graph Coloring

Online Graph Coloring is a computational problem in graph theory where vertices of a graph are revealed sequentially and must be irrevocably assigned colors from a fixed palette in real time, such that no two adjacent vertices share the same color, with the coloring decision constrained by the lack of knowledge about future vertices.

33

Publications

960

Citations

84

Authors

48

Institutions

Publications per year

2017–2026

1

Parents

Publications

33

An on-line graph coloring algorithm with sublinear performance ratio

László Lovász, Michael Saks, W. T. Trotter · Discrete Mathematics · 1989 · 135 citations

, , +9

A fast algorithm for equitable coloring

Henry A. Kiersteád, Alexandr Kostochka, Marcelo Mydlarz et al. · COMBINATORICA · 2010 · 88 citations

, , +7

Randomized online graph coloring

Sundar Vishwanathan · Journal of Algorithms · 1992 · 55 citations

, , +16

On dynamic coloring for planar graphs and graphs of higher genus

Ye Chen, Suohai Fan, Hong‐Jian Lai et al. · Discrete Applied Mathematics · 2012 · 48 citations

, , +12

An Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms

Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri · Algorithmica · 2004 · 35 citations

, , +12

1–5 of 33

Authors

84

  1. SS
    Shakhar Smorodinsky

    Tel Aviv University, Israel

    4 publications · 93 citations

    4

    h-index

  2. AB
    Amotz Bar-Noy

    IBM (United States), United States

    3 publications · 75 citations

    3

    h-index

  3. PC
    Panagiotis Cheilaris

    Ben-Gurion University of the Negev, Israel

    3 publications · 75 citations

    3

    h-index

  4. RS
    Reto Spöhel

    ETH Zurich, Switzerland

    3 publications · 72 citations

    3

    h-index

  5. MG
    Maya Gokhale

    Lawrence Livermore National Laboratory, United States

    2 publications · 40 citations

    2

    h-index

1–5 of 84

Institutions

48

  1. Tel Aviv University

    Tel Aviv, Israel

    5 h-index

    9 publications

    185 citations

  2. ETH Zurich

    Zurich, Switzerland

    5 h-index

    13 publications

    314 citations

  3. Ben-Gurion University of the Negev

    Beersheba, Israel

    4 h-index

    6 publications

    121 citations

  4. Princeton University

    Princeton, United States

    2 h-index

    2 publications

    157 citations

  5. Brooklyn College

    Brooklyn, United States

    2 h-index

    2 publications

    55 citations

  6. Arizona State University

    Tempe, United States

    2 h-index

    2 publications

    223 citations

  7. University of Chicago

    Chicago, United States

    2 h-index

    2 publications

    74 citations

  8. Rutgers, The State University of New Jersey

    New Brunswick, United States

    2 h-index

    2 publications

    223 citations

1–8 of 48

Venues

  1. Journal of Algorithms

    3 publications · 104 citations

    3

    h-index

  2. Combinatorics Probability Computing

    3 publications · 86 citations

    3

    h-index

  3. Discrete Applied Mathematics

    2 publications · 66 citations

    2

    h-index

  4. The Electronic Journal of Combinatorics

    2 publications · 38 citations

    2

    h-index

  5. ACM Transactions on Algorithms

    TALG · 2 publications · 49 citations

    2

    h-index

1–5