Distributed minimum vertex coloring and maximum independent set in chordal graphs

Christian Konrad; Viktor Zamaraev

doi:10.1016/j.tcs.2022.04.047

Distributed minimum vertex coloring and maximum independent set in chordal graphs

Christian Konrad, Viktor Zamaraev

Department of Computer Science

Research output: Contribution to journal › Article (Academic Journal) › peer-review

2 Citations (Scopus)

41 Downloads (Pure)

Original language	English
Pages (from-to)	486-502
Number of pages	17
Journal	Theoretical Computer Science
Volume	922
Early online date	29 Apr 2022
DOIs	https://doi.org/10.1016/j.tcs.2022.04.047
Publication status	Published - 2022

Bibliographical note

Funding Information:
C. Konrad carried out most work on this paper while being at the University of Warwick. He was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at Warwick University and by EPSRC award EP/N011163/1. V. Zamaraev carried out most work on this paper while being at Durham University. He was supported by EPSRC award EP/P020372/1. A preliminary version of this work appeared as a brief announcement in the Proceedings of PODC 2018 [23], and as a conference paper in the Proceedings of MFCS 2019 [24].

Funding Information:
C. Konrad carried out most work on this paper while being at the University of Warwick. He was supported by the Centre for Discrete Mathematics and its Applications ( DIMAP ) at Warwick University and by EPSRC award EP/N011163/1 . V. Zamaraev carried out most work on this paper while being at Durham University. He was supported by EPSRC award EP/P020372/1 . A preliminary version of this work appeared as a brief announcement in the Proceedings of PODC 2018 [23] , and as a conference paper in the Proceedings of MFCS 2019 [24] .

Publisher Copyright:
© 2022 The Authors

Access to Document

10.1016/j.tcs.2022.04.047Licence: CC BY

Full-text PDF (final published version)
This is the final published version of the article (version of record). It first appeared online via Elsevier at https://doi.org/10.1016/j.tcs.2022.04.047 . Please refer to any applicable terms of use of the publisher.
Final published version, 595 KBLicence: CC BY

Handle.net

Persistent link

Cite this

@article{35a59b12f108432281af334a5cb974c0,

title = "Distributed minimum vertex coloring and maximum independent set in chordal graphs",

author = "Christian Konrad and Viktor Zamaraev",

note = "Funding Information: C. Konrad carried out most work on this paper while being at the University of Warwick. He was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at Warwick University and by EPSRC award EP/N011163/1. V. Zamaraev carried out most work on this paper while being at Durham University. He was supported by EPSRC award EP/P020372/1. A preliminary version of this work appeared as a brief announcement in the Proceedings of PODC 2018 [23], and as a conference paper in the Proceedings of MFCS 2019 [24]. Funding Information: C. Konrad carried out most work on this paper while being at the University of Warwick. He was supported by the Centre for Discrete Mathematics and its Applications ( DIMAP ) at Warwick University and by EPSRC award EP/N011163/1 . V. Zamaraev carried out most work on this paper while being at Durham University. He was supported by EPSRC award EP/P020372/1 . A preliminary version of this work appeared as a brief announcement in the Proceedings of PODC 2018 [23] , and as a conference paper in the Proceedings of MFCS 2019 [24] . Publisher Copyright: {\textcopyright} 2022 The Authors",

year = "2022",

doi = "10.1016/j.tcs.2022.04.047",

language = "English",

volume = "922",

pages = "486--502",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Amsterdam:Elsevier",

}

TY - JOUR

T1 - Distributed minimum vertex coloring and maximum independent set in chordal graphs

AU - Konrad, Christian

AU - Zamaraev, Viktor

N1 - Funding Information: C. Konrad carried out most work on this paper while being at the University of Warwick. He was supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at Warwick University and by EPSRC award EP/N011163/1. V. Zamaraev carried out most work on this paper while being at Durham University. He was supported by EPSRC award EP/P020372/1. A preliminary version of this work appeared as a brief announcement in the Proceedings of PODC 2018 [23], and as a conference paper in the Proceedings of MFCS 2019 [24]. Funding Information: C. Konrad carried out most work on this paper while being at the University of Warwick. He was supported by the Centre for Discrete Mathematics and its Applications ( DIMAP ) at Warwick University and by EPSRC award EP/N011163/1 . V. Zamaraev carried out most work on this paper while being at Durham University. He was supported by EPSRC award EP/P020372/1 . A preliminary version of this work appeared as a brief announcement in the Proceedings of PODC 2018 [23] , and as a conference paper in the Proceedings of MFCS 2019 [24] . Publisher Copyright: © 2022 The Authors

PY - 2022

Y1 - 2022

U2 - 10.1016/j.tcs.2022.04.047

DO - 10.1016/j.tcs.2022.04.047

M3 - Article (Academic Journal)

SN - 0304-3975

VL - 922

SP - 486

EP - 502

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -