Chain method for panchromatic colorings of hypergraphs

Margarita Akhmejanova; József Balogh; Dmitrii Shabanov

doi:10.1016/j.dam.2022.06.005

Chain method for panchromatic colorings of hypergraphs

Margarita Akhmejanova, József Balogh, Dmitrii Shabanov

Mathematics

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

Abstract

We deal with an extremal problem concerning panchromatic colorings of hypergraphs. A vertex r-coloring of a hypergraph H is panchromatic if every edge meets every color. We prove that for every [Formula presented], every n-uniform hypergraph H with [Formula presented] has a panchromatic coloring with r colors, where c>0 is an absolute constant.

Original language	English (US)
Pages (from-to)	72-81
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	321
DOIs	https://doi.org/10.1016/j.dam.2022.06.005
State	Published - Nov 15 2022

Keywords

Panchromatic coloring
Proper coloring
Property B
Uniform hypergraph

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.1016/j.dam.2022.06.005

Library availability

Discover UIUC Full Text

Cite this

@article{e0c2fbc78a0040a9b40a4cd030a28360,

title = "Chain method for panchromatic colorings of hypergraphs",

abstract = "We deal with an extremal problem concerning panchromatic colorings of hypergraphs. A vertex r-coloring of a hypergraph H is panchromatic if every edge meets every color. We prove that for every [Formula presented], every n-uniform hypergraph H with [Formula presented] has a panchromatic coloring with r colors, where c>0 is an absolute constant.",

keywords = "Panchromatic coloring, Proper coloring, Property B, Uniform hypergraph",

author = "Margarita Akhmejanova and J{\'o}zsef Balogh and Dmitrii Shabanov",

note = "The work of the first and the third authors was funded by Russian Foundation for Basic Research No. 20-31-70039 and No. 20-31-90029 and the Council for the Support of Leading Scientific Schools of the President of the Russian Federation No. N.Sh.-775.2022.1.1 . The first author is a Young Russian Mathematics award winner and would like to thank its sponsors and jury.",

year = "2022",

month = nov,

day = "15",

doi = "10.1016/j.dam.2022.06.005",

language = "English (US)",

volume = "321",

pages = "72--81",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Chain method for panchromatic colorings of hypergraphs

AU - Akhmejanova, Margarita

AU - Balogh, József

AU - Shabanov, Dmitrii

N1 - The work of the first and the third authors was funded by Russian Foundation for Basic Research No. 20-31-70039 and No. 20-31-90029 and the Council for the Support of Leading Scientific Schools of the President of the Russian Federation No. N.Sh.-775.2022.1.1 . The first author is a Young Russian Mathematics award winner and would like to thank its sponsors and jury.

PY - 2022/11/15

Y1 - 2022/11/15

N2 - We deal with an extremal problem concerning panchromatic colorings of hypergraphs. A vertex r-coloring of a hypergraph H is panchromatic if every edge meets every color. We prove that for every [Formula presented], every n-uniform hypergraph H with [Formula presented] has a panchromatic coloring with r colors, where c>0 is an absolute constant.

AB - We deal with an extremal problem concerning panchromatic colorings of hypergraphs. A vertex r-coloring of a hypergraph H is panchromatic if every edge meets every color. We prove that for every [Formula presented], every n-uniform hypergraph H with [Formula presented] has a panchromatic coloring with r colors, where c>0 is an absolute constant.

KW - Panchromatic coloring

KW - Proper coloring

KW - Property B

KW - Uniform hypergraph

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

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

U2 - 10.1016/j.dam.2022.06.005

DO - 10.1016/j.dam.2022.06.005

M3 - Article

AN - SCOPUS:85133279354

SN - 0166-218X

VL - 321

SP - 72

EP - 81

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Chain method for panchromatic colorings of hypergraphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this