Linear Ramsey numbers

Aistis Atminas; Vadim Lozin; Viktor Zamaraev

doi:10.1007/978-3-319-94667-2_3

Linear Ramsey numbers

Aistis Atminas, Vadim Lozin^*, Viktor Zamaraev

^*Corresponding author for this work

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

2 Citations (Scopus)

Abstract

The Ramsey number R_X(p, q) for a class of graphs X is the minimum n such that every graph in X with at least n vertices has either a clique of size p or an independent set of size q. We say that Ramsey number is linear in X if there is a constant k such that R_X(p, q) ≤k(p+q) for all p, q. In the present paper we conjecture that Ramsey number is linear in X if and only if the co-chromatic number is bounded in X and determine Ramsey numbers for several classes of graphs that verify the conjecture.

Original language	English
Title of host publication	Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings
Editors	Hon Wai Leong, Costas Iliopoulos, Wing-Kin Sung
Publisher	Springer Verlag
Pages	26-38
Number of pages	13
ISBN (Print)	9783319946665
DOIs	https://doi.org/10.1007/978-3-319-94667-2_3
Publication status	Published - 2018
Externally published	Yes
Event	29th International Workshop on Combinatorial Algorithms, IWOCA 2018 - Singapore, Singapore Duration: 16 Jul 2018 → 19 Jul 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10979 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th International Workshop on Combinatorial Algorithms, IWOCA 2018
Country/Territory	Singapore
City	Singapore
Period	16/07/18 → 19/07/18

Access to Document

10.1007/978-3-319-94667-2_3

Cite this

Atminas, A., Lozin, V., & Zamaraev, V. (2018). Linear Ramsey numbers. In H. W. Leong, C. Iliopoulos, & W.-K. Sung (Eds.), Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings (pp. 26-38). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10979 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-94667-2_3

Atminas, Aistis ; Lozin, Vadim ; Zamaraev, Viktor. / Linear Ramsey numbers. Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings. editor / Hon Wai Leong ; Costas Iliopoulos ; Wing-Kin Sung. Springer Verlag, 2018. pp. 26-38 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{23654da4f0894bf0898ba9876e4aedcf,

title = "Linear Ramsey numbers",

abstract = "The Ramsey number RX(p, q) for a class of graphs X is the minimum n such that every graph in X with at least n vertices has either a clique of size p or an independent set of size q. We say that Ramsey number is linear in X if there is a constant k such that RX(p, q) ≤k(p+q) for all p, q. In the present paper we conjecture that Ramsey number is linear in X if and only if the co-chromatic number is bounded in X and determine Ramsey numbers for several classes of graphs that verify the conjecture.",

author = "Aistis Atminas and Vadim Lozin and Viktor Zamaraev",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 29th International Workshop on Combinatorial Algorithms, IWOCA 2018 ; Conference date: 16-07-2018 Through 19-07-2018",

year = "2018",

doi = "10.1007/978-3-319-94667-2_3",

language = "English",

isbn = "9783319946665",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "26--38",

editor = "Leong, {Hon Wai} and Costas Iliopoulos and Wing-Kin Sung",

booktitle = "Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings",

}

Atminas, A, Lozin, V & Zamaraev, V 2018, Linear Ramsey numbers. in HW Leong, C Iliopoulos & W-K Sung (eds), Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10979 LNCS, Springer Verlag, pp. 26-38, 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, Singapore, Singapore, 16/07/18. https://doi.org/10.1007/978-3-319-94667-2_3

Linear Ramsey numbers. / Atminas, Aistis; Lozin, Vadim; Zamaraev, Viktor.
Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings. ed. / Hon Wai Leong; Costas Iliopoulos; Wing-Kin Sung. Springer Verlag, 2018. p. 26-38 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10979 LNCS).

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

TY - GEN

T1 - Linear Ramsey numbers

AU - Atminas, Aistis

AU - Lozin, Vadim

AU - Zamaraev, Viktor

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - The Ramsey number RX(p, q) for a class of graphs X is the minimum n such that every graph in X with at least n vertices has either a clique of size p or an independent set of size q. We say that Ramsey number is linear in X if there is a constant k such that RX(p, q) ≤k(p+q) for all p, q. In the present paper we conjecture that Ramsey number is linear in X if and only if the co-chromatic number is bounded in X and determine Ramsey numbers for several classes of graphs that verify the conjecture.

AB - The Ramsey number RX(p, q) for a class of graphs X is the minimum n such that every graph in X with at least n vertices has either a clique of size p or an independent set of size q. We say that Ramsey number is linear in X if there is a constant k such that RX(p, q) ≤k(p+q) for all p, q. In the present paper we conjecture that Ramsey number is linear in X if and only if the co-chromatic number is bounded in X and determine Ramsey numbers for several classes of graphs that verify the conjecture.

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

U2 - 10.1007/978-3-319-94667-2_3

DO - 10.1007/978-3-319-94667-2_3

M3 - Conference Proceeding

AN - SCOPUS:85049917698

SN - 9783319946665

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 26

EP - 38

BT - Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings

A2 - Leong, Hon Wai

A2 - Iliopoulos, Costas

A2 - Sung, Wing-Kin

PB - Springer Verlag

T2 - 29th International Workshop on Combinatorial Algorithms, IWOCA 2018

Y2 - 16 July 2018 through 19 July 2018

ER -

Atminas A, Lozin V, Zamaraev V. Linear Ramsey numbers. In Leong HW, Iliopoulos C, Sung WK, editors, Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings. Springer Verlag. 2018. p. 26-38. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-94667-2_3

Linear Ramsey numbers

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this