论文标题
局部不规则猜想与仙人掌
Local Irregularity Conjecture vs. cacti
论文作者
论文摘要
如果每个边缘的最终偏见的程度都不同，则图是局部不规则的。如果每种颜色诱导G的局部不规则亚图。可着色图G的局部不规则色索引X'irr（g）是G的局部不规则边缘着色所需的最小颜色。局部不规则性猜想声称，所有可着色图最多都需要3种颜色，以使本地不规则的边缘着色。最近，已经观察到，猜想对弓形图b不满意[7]。仙人掌是该猜想的重要图形类别，因为B和所有不可色的图都是仙人掌。在本文中，我们表明，对于每一个可着色的仙人掌图g！= b，它认为x'irr（g）<= 3。这使我们相信b是唯一具有X'irr（b）> 3的可色彩图，因此B是本地违规性猜想的唯一反例。
A graph is locally irregular if the degrees of the end-vertices of every edge are distinct. An edge coloring of a graph G is locally irregular if every color induces a locally irregular subgraph of G. A colorable graph G is any graph which admits a locally irregular edge coloring. The locally irregular chromatic index X'irr(G) of a colorable graph G is the smallest number of colors required by a locally irregular edge coloring of G. The Local Irregularity Conjecture claims that all colorable graphs require at most 3 colors for locally irregular edge coloring. Recently, it has been observed that the conjecture does not hold for the bow-tie graph B [7]. Cacti are important class of graphs for this conjecture since B and all non-colorable graphs are cacti. In this paper we show that for every colorable cactus graph G != B it holds that X'irr(G) <= 3. This makes us to believe that B is the only colorable graph with X'irr(B) > 3, and consequently that B is the only counterexample to the Local Irregularity Conjecture.
