Largest subgraph from a hereditary property in a random graph

Noga Alon; Michael Krivelevich; Wojciech Samotij

doi:10.1016/j.disc.2023.113480

Largest subgraph from a hereditary property in a random graph

Noga Alon, Michael Krivelevich, Wojciech Samotij

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Let P be a non-trivial hereditary property of graphs and let k be the minimum chromatic number of a graph that does not belong to P.

Original language	English (US)
Article number	113480
Journal	Discrete Mathematics
Volume	346
Issue number	9
DOIs	https://doi.org/10.1016/j.disc.2023.113480
State	Published - Sep 2023

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Hereditary property
Random graphs
Subgraphs

Access to Document

10.1016/j.disc.2023.113480

Cite this

@article{adf1b0ee7e85412fa2723dc9294311a9,

title = "Largest subgraph from a hereditary property in a random graph",

abstract = "Let P be a non-trivial hereditary property of graphs and let k be the minimum chromatic number of a graph that does not belong to P.",

keywords = "Hereditary property, Random graphs, Subgraphs",

author = "Noga Alon and Michael Krivelevich and Wojciech Samotij",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2023",

month = sep,

doi = "10.1016/j.disc.2023.113480",

language = "English (US)",

volume = "346",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "9",

}

TY - JOUR

T1 - Largest subgraph from a hereditary property in a random graph

AU - Alon, Noga

AU - Krivelevich, Michael

AU - Samotij, Wojciech

PY - 2023/9

Y1 - 2023/9

N2 - Let P be a non-trivial hereditary property of graphs and let k be the minimum chromatic number of a graph that does not belong to P.

AB - Let P be a non-trivial hereditary property of graphs and let k be the minimum chromatic number of a graph that does not belong to P.

KW - Hereditary property

KW - Random graphs

KW - Subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85153798598&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85153798598&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2023.113480

DO - 10.1016/j.disc.2023.113480

M3 - Article

AN - SCOPUS:85153798598

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9

M1 - 113480

ER -

Largest subgraph from a hereditary property in a random graph

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this