论文标题
没有诱导房屋或诱导孔的图形具有de bruijn-erds属性
Graphs with no induced house nor induced hole have the de Bruijn-Erdős property
论文作者
论文摘要
平面中的一组n个点并非全部界线定义至少n个不同的线。 Chen和Chvátal在2008年提出，在有限的度量空间的更广泛背景下可以实现类似的结果。对于图指标，该猜想仍然开放。在本文中，我们证明没有诱导房屋或诱发长度的图形至少〜5验证所需的特性。我们专注于由顶点在距离处产生的线，最多是2，定义了一个新的``良好对''的概念，该概念可能在较大的家庭中应用，最后使用放电技术来计数不可约图中的线。
A set of n points in the plane which are not all collinear defines at least n distinct lines. Chen and Chvátal conjectured in 2008 that a similar result can be achieved in the broader context of finite metric spaces. This conjecture remains open even for graph metrics. In this article we prove that graphs with no induced house nor induced cycle of length at least~5 verify the desired property. We focus on lines generated by vertices at distance at most 2, define a new notion of ``good pairs'' that might have application in larger families, and finally use a discharging technique to count lines in irreducible graphs.
