Abstract
dc:description.abstractWe naturally extend Bollobas's classical method and result about the chromatic number of random graphs chi(G(n,p)) ~ n/log_b(n) (for p constant, b=1/(1-p)) to the chromatic number of random signed graphs to obtain chi(G(n,p,q)) ~ n/log_b(n) (for p constant, b=1/(1-p), q=o(1)). We also give a sufficient bound on q under which a.a.s. the chromatic number of G(n,p,q) is unchanged before and after adding negative edges.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Yuan, Dao Chen
- Advisor dc:contributor.advisor
-
- Penny, Haxell
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/20537