论文标题
特殊挖掘的定向顶点和弧色的有效计算
Efficient computation of oriented vertex and arc colorings of special digraphs
论文作者
论文摘要
在本文中，我们研究了与众所周知的串联平行图有关的边缘串联挖掘图（ESP-Digraphs）上的定向顶点和弧色问题。串联平行图是图形，具有两个称为终端的特殊顶点，通过并行和串联组成递归形成。这些图在建模系列和平行电路中具有应用，并且在理论计算机科学中也起着重要作用。定向的一类平行挖掘图是由通过单个弧连接并应用并行和串联组成的顶点对递归定义的，这导致了未指向的串联式 - 平行图的特定方向。此外，我们考虑了边缘系列平行挖掘的线挖掘图，这些图被称为最小串联 - 平行挖掘图（MSP-Digraphs）。 我们显示了定向色数的紧密上限以及边缘串联挖掘和最小串联挖掘图的定向色素指数。此外，我们引入了第一个线性时间解决方案，用于计算定向色的边缘串联 - 平行挖掘图和最小串联串联挖掘的定向色素指数。
In this paper we study the oriented vertex and arc coloring problem on edge series-parallel digraphs (esp-digraphs) which are related to the well known series-parallel graphs. Series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by parallel and series composition. These graphs have applications in modeling series and parallel electric circuits and also play an important role in theoretical computer science. The oriented class of series-parallel digraphs is recursively defined from pairs of vertices connected by a single arc and applying the parallel and series composition, which leads to specific orientations of undirected series-parallel graphs. Further we consider the line digraphs of edge series-parallel digraphs, which are known as minimal series-parallel digraphs (msp-digraphs). We show tight upper bounds for the oriented chromatic number and the oriented chromatic index of edge series-parallel digraphs and minimal series-parallel digraphs. Furthermore, we introduce first linear time solutions for computing the oriented chromatic number of edge series-parallel digraphs and the oriented chromatic index of minimal series-parallel digraphs.
