论文标题
签名1和2的图形的边缘着色
Edge coloring of graphs of signed class 1 and 2
论文作者
论文摘要
最近，Behr介绍了签名图的色度索引的概念，并证明了每个签名的图形$（g $，$σ）$的概念。 δ（g）\leqχ'（g \ text {，}σ）\leqΔ（g）+1 \ text {，} \]，其中$δ（g）$是$ g $的最大度，$ g $，$ c'$表示其色度索引。 通常，$（g $，$σ）$的色度指数取决于基础图$ g $和签名$σ$。在论文中，我们研究$χ'（g $，$σ）$的图形$ g $不取决于$σ$。为此，我们介绍了两个新的图表，即$ 1^\ pm $和$ 2^\ pm $，使得$ g $是$ 1^\ pm $的$ 1^\ pm $（分别为$ 2^\ pm $），并且仅当$χ'（g $，$σ）=Δ=δ（g）$（分别为$ c $，$χ'（g $，g $，g $ q）= g $，$ qu， $σ$。我们证明，所有车轮，项链，完整的两部分图$ k_ {r，t} $带有$ r \ neq t $，几乎所有仙人掌图都是$ 1^\ pm $。此外，我们给出了足够和必要的条件，使图的图形为$ 2^\ pm $，即我们表明这些图必须具有奇怪的最大程度，并给出了具有任意奇数最大程度的此类图的示例，该图是$ 1 $。
Recently, Behr introduced a notion of the chromatic index of signed graphs and proved that for every signed graph $(G$, $σ)$ it holds that \[ Δ(G)\leqχ'(G\text{, }σ)\leqΔ(G)+1\text{,} \] where $Δ(G)$ is the maximum degree of $G$ and $χ'$ denotes its chromatic index. In general, the chromatic index of $(G$, $σ)$ depends on both the underlying graph $G$ and the signature $σ$. In the paper we study graphs $G$ for which $χ'(G$, $σ)$ does not depend on $σ$. To this aim we introduce two new classes of graphs, namely $1^\pm$ and $2^\pm$, such that graph $G$ is of class $1^\pm$ (respectively, $2^\pm$) if and only if $χ'(G$, $σ)=Δ(G)$ (respectively, $χ'(G$, $σ)=Δ(G)+1$) for all possible signatures $σ$. We prove that all wheels, necklaces, complete bipartite graphs $K_{r,t}$ with $r\neq t$ and almost all cacti graphs are of class $1^\pm$. Moreover, we give sufficient and necessary conditions for a graph to be of class $2^\pm$, i.e. we show that these graphs must have odd maximum degree and give examples of such graphs with arbitrary odd maximum degree bigger that $1$.
