关于边密度分布良好的图.pdfVIP

关于边密度分布良好的图

SyedMujtabaHassan∗ShahidHussain†

2024年3月21日

摘要

在本文中，我们介绍了一类图，我们将这类图称为平均遗传图。许多通常出现在图论应用中的图都属于

此类别。许多流行的图类型也归于这一类别，例如正则图、树和其他流行的图类别。本文旨在探讨一些关于

本着色平均遗传图的有趣性质。我们证明了一个新的上界，即通过其最大平均度数来表示一个图的色数，并表

明这个界限优于之前的界限。从这一点出发，我们展示了平均度数和平均遗传图的色数之间的关系。然后，

译我们展示即使有了新界限，当输入受限于平均遗传图时，图3-coloring问题仍然是NP-hard。我们提供

中了一个图是平均遗传的一个等价条件，通过这一点，我们表明可以在线性时间内判断给定的图是否为平均遗

传性。

3

v关键词：图论，图着色，NP难图问题，图平均度数

3

0

8

61介绍

0

.

2我们引入了一类新的图，称之为平均遗传图。关于这类图的着色有许多有趣的性质，本文探讨了其中

0

4的一部分。我们提供了一个新上界来表示一个图的色数，用其最大平均度来衡量，即MAD

2

:，我们证明这个界限优于之前已知的结果。我们利用这一界限找到了一个图的平均度与其色数之间的

v

i关系，从这一点出发，我们证明了对于某一类情况，我们知道该平均遗传图的确切色数。然而，尽管有

x

r这些结果，在输入限制为平均遗传图的情况下，3-coloring图的问题仍然是NP-hard。我们在第4节

a

中展示了这一点。这个结果对我们研究图3-coloring问题的复杂性二分法感兴趣。

我们将分析判断一个图是否为平均遗传性的计算复杂性，并展示我们可以在线性时间内计算出一个

图是否为平均遗传性。这是通过提供一个图成为平均遗传性的等价条件来实现的。有趣的是，平均遗传

性图的类别相当广泛，因为它包含了许多在应用中常见的流行图类，如树、正则图等等。所以这个类别

只限制了一些极端情况。

我们论文的主要结果是对图的色数给出了一个新的广义上界，这比文献中先前找到的界限有了改

进。

1.1预备知识

在整个文档中，我们将图表示为，其中是一个顶点集为和边集为的图。一条边

表示为集合，其中和属于，使得。此外，对于图，我们使用表示的顶点

∗ms06948@.pk,ComputerScienceDepartment,HabibUniversity,Karachi,Pakistan(correspondingauthor)

†shahidhussain@.pk,ComputerScienceDepartment,InstituteofBusinessAdministration,Karachi,Pakistan

1

集，使用表示的边集。这里考虑的所有图形都是无向且简单的，意味着它们不包含环、多重边

或有向边。我们将使用表示的一个导出子图。对于某些，表示通过移除中

的顶点而获得的的子图。对于，表示图。对于每个顶点，我们使用

来表示在中的度。我们还使用表示的最大度数，并使用表示的最小度数。的平

均度，记为，是所有度的平均值，可以通过计算得出，如果非空的

话。对于一个零图，我们定义其平均度