On the power of choice for k-colorability of random graphs

Varsha Dani; Diksha Gupta; Thomas P. Hayes

doi:10.4230/LIPIcs-APPROX/RANDOM.2021.59

On the power of choice for k-colorability of random graphs

Varsha Dani
, Diksha Gupta
, Thomas P. Hayes

Department of Computer Science and Engineering

Ronin Institute
Rochester Institute of Technology
National University of Singapore

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In an r-choice Achlioptas process, random edges are generated r at a time, and an online strategy is used to select one of them for inclusion in a graph. We investigate the problem of whether such a selection strategy can shift the k-colorability transition; that is, the number of edges at which the graph goes from being k-colorable to non-k-colorable. We show that, for k ≥ 9, two choices suffice to delay the k-colorability threshold, and that for every k ≥ 2, six choices suffice.

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021
Editors	Mary Wootters, Laura Sanita
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959772075
DOIs	https://doi.org/10.4230/LIPIcs-APPROX/RANDOM.2021.59
State	Published - Sep 1 2021
Event	24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 - Virtual, Seattle, United States Duration: Aug 16 2021 → Aug 18 2021

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	207
ISSN (Print)	1868-8969

Conference

Conference	24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021
Country/Territory	United States
City	Virtual, Seattle
Period	08/16/21 → 08/18/21

Keywords

Achlioptas processes
Graph colorability
Phase transition
Random graphs

Access to Document

10.4230/LIPIcs-APPROX/RANDOM.2021.59

Cite this

Dani, V., Gupta, D., & Hayes, T. P. (2021). On the power of choice for k-colorability of random graphs. In M. Wootters, & L. Sanita (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021 Article 59 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 207). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs-APPROX/RANDOM.2021.59

Dani, Varsha ; Gupta, Diksha ; Hayes, Thomas P. / On the power of choice for k-colorability of random graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. editor / Mary Wootters ; Laura Sanita. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{352d360ff58a49618346c03f7b000535,

title = "On the power of choice for k-colorability of random graphs",

abstract = "In an r-choice Achlioptas process, random edges are generated r at a time, and an online strategy is used to select one of them for inclusion in a graph. We investigate the problem of whether such a selection strategy can shift the k-colorability transition; that is, the number of edges at which the graph goes from being k-colorable to non-k-colorable. We show that, for k ≥ 9, two choices suffice to delay the k-colorability threshold, and that for every k ≥ 2, six choices suffice.",

keywords = "Achlioptas processes, Graph colorability, Phase transition, Random graphs",

author = "Varsha Dani and Diksha Gupta and Hayes, \{Thomas P.\}",

note = "Publisher Copyright: {\textcopyright} Varsha Dani, Diksha Gupta, and Thomas P. Hayes; licensed under Creative Commons License CC-BY 4.0; 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 ; Conference date: 16-08-2021 Through 18-08-2021",

year = "2021",

month = sep,

day = "1",

doi = "10.4230/LIPIcs-APPROX/RANDOM.2021.59",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Mary Wootters and Laura Sanita",

booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021",

}

Dani, V, Gupta, D & Hayes, TP 2021, On the power of choice for k-colorability of random graphs. in M Wootters & L Sanita (eds), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021., 59, Leibniz International Proceedings in Informatics, LIPIcs, vol. 207, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021, Virtual, Seattle, United States, 08/16/21. https://doi.org/10.4230/LIPIcs-APPROX/RANDOM.2021.59

On the power of choice for k-colorability of random graphs. / Dani, Varsha; Gupta, Diksha; Hayes, Thomas P.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. ed. / Mary Wootters; Laura Sanita. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 59 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 207).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the power of choice for k-colorability of random graphs

AU - Dani, Varsha

AU - Gupta, Diksha

AU - Hayes, Thomas P.

N1 - Publisher Copyright: © Varsha Dani, Diksha Gupta, and Thomas P. Hayes; licensed under Creative Commons License CC-BY 4.0

PY - 2021/9/1

Y1 - 2021/9/1

N2 - In an r-choice Achlioptas process, random edges are generated r at a time, and an online strategy is used to select one of them for inclusion in a graph. We investigate the problem of whether such a selection strategy can shift the k-colorability transition; that is, the number of edges at which the graph goes from being k-colorable to non-k-colorable. We show that, for k ≥ 9, two choices suffice to delay the k-colorability threshold, and that for every k ≥ 2, six choices suffice.

AB - In an r-choice Achlioptas process, random edges are generated r at a time, and an online strategy is used to select one of them for inclusion in a graph. We investigate the problem of whether such a selection strategy can shift the k-colorability transition; that is, the number of edges at which the graph goes from being k-colorable to non-k-colorable. We show that, for k ≥ 9, two choices suffice to delay the k-colorability threshold, and that for every k ≥ 2, six choices suffice.

KW - Achlioptas processes

KW - Graph colorability

KW - Phase transition

KW - Random graphs

UR - https://www.scopus.com/pages/publications/85115633785

U2 - 10.4230/LIPIcs-APPROX/RANDOM.2021.59

DO - 10.4230/LIPIcs-APPROX/RANDOM.2021.59

M3 - Conference contribution

AN - SCOPUS:85115633785

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021

A2 - Wootters, Mary

A2 - Sanita, Laura

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021

Y2 - 16 August 2021 through 18 August 2021

ER -

Dani V, Gupta D, Hayes TP. On the power of choice for k-colorability of random graphs. In Wootters M, Sanita L, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2021. 59. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs-APPROX/RANDOM.2021.59

On the power of choice for k-colorability of random graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this