论文标题
局部二分图的色谱
The chromatic profile of locally bipartite graphs
论文作者
论文摘要
1973年，Erdős和Simonovits询问了最低度最低度大于$ 1/3 \ cdot n $的每$ n $ vertex三角形图是否3色。这个问题启动了无三角形图的色轮廓的研究：对于每个$ k $，最低学位可以保证无三角形的图为$ k $ - 颜色。这个问题具有丰富的历史，这最终导致了勃兰特和托马斯的完整解决方案。关于$ h $ fr的$ h $的$ h $ free图的色谱显示，知之甚少。 无三角形的图是每个邻域都是一个色的图形。 Luczak和Thomassé首先提到的本地二手图是每个邻域是双方的自然变体。在这里，我们研究了局部两部分图的色谱。我们表明，最低度大于$ 4/7 \ cdot n $的每$ N $ vertex本地两分图都可以3色（$ 4/7 $紧密），最低度大于$ 6/11 \ cdot n $是4色。尽管局部二分和三角形图的色谱曲线具有一些相似之处，但我们会看到存在明显的差异。
In 1973, Erdős and Simonovits asked whether every $n$-vertex triangle-free graph with minimum degree greater than $1/3 \cdot n$ is 3-colourable. This question initiated the study of the chromatic profile of triangle-free graphs: for each $k$, what minimum degree guarantees that a triangle-free graph is $k$-colourable. This problem has a rich history which culminated in its complete solution by Brandt and Thomassé. Much less is known about the chromatic profile of $H$-free graphs for general $H$. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. Locally bipartite graphs, first mentioned by Luczak and Thomassé, are the natural variant of triangle-free graphs in which each neighbourhood is bipartite. Here we study the chromatic profile of locally bipartite graphs. We show that every $n$-vertex locally bipartite graph with minimum degree greater than $4/7 \cdot n$ is 3-colourable ($4/7$ is tight) and with minimum degree greater than $6/11 \cdot n$ is 4-colourable. Although the chromatic profiles of locally bipartite and triangle-free graphs bear some similarities, we will see there are striking differences.
