This article is available for purchase or by subscription. See below.
Abstract
|
The paper deals with strong
-colorings
of a random
-uniform hypergraph
in the binomial model
.
A vertex coloring is said to be strong for a hypergraph if any two
vertices that share a common edge are colored with distinct colors. We
consider the sparse case when the expected number of edges is equal to
and the
values
,
remain constant as
. We prove tight bounds
for the strong
-colorability
threshold as the bounds for the parameter
. As a corollary
we give the explicit limit value of the strong chromatic number of the random hypergraph
for almost all values
of the parameter
.
|
PDF Access Denied
We have not been able to recognize your IP address
18.223.107.124
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journal-recommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for
USD 40.00:
Keywords
random hypergraphs, strong colorings, probability
thresholds, second-moment method
|
Mathematical Subject Classification
Primary: 05C15, 05C80
|
Milestones
Received: 3 December 2021
Revised: 17 September 2022
Accepted: 2 October 2022
Published: 29 March 2023
|
© 2023 MSP (Mathematical Sciences
Publishers). |
|