论文标题
公平的$ d $ - 定格的图形可选性
Equitable $d$-degenerate choosability of graphs
论文作者
论文摘要
令$ {\ Mathcal d} _d $为$ d $ -Degenate图的类，让$ l $为图$ g $的列表分配。 $ g $的颜色使每个顶点从其列表中接收颜色，而用一种颜色的顶点引起的子图是$ d $ - 基本图，称为$（l，{\ Mathcal d} _d _d）$ - $ g $的颜色。对于$ k $ - 统一列表分配$ l $和$ d \ in \ athbb {n} _0 $，图$ g $是公平的$（l，{\ mathcal d} _d）$ - 可颜色 - 如果有$（l，l，l，{\ mathcal d} _d} _d _d）$ go $ colder of coldy nos size size size size size size nos yondy的颜色$ \ left \ lceil | v（g）|/k \ right \ rceil $。公平的$（l，{\ Mathcal d} _d）$ - 着色是对公平列表着色的概括，由Kostochka在Al。引入，以及Zhang提出的公平列表Arboricity。这种模型在施加子网上某些结构属性的网络分解中可能很有用。 在本文中，我们给出了一种多项式时间算法，对于给定的$（k，d）$ - $ g $的分区，带有$ t $ - 均匀的列表分配$ l $和$ t \ geq k $，返回其公平$（l，\ nathcal {d} _ {d-1} _ {d-1} _ {d-1}）$ - 彩色。此外，我们表明3维网格是公平的$（l，\ Mathcal {d} _1）$ - 适用于任何$ t $ rustriction list list分配$ l $ whene $ t \ geq 3 $。
Let ${\mathcal D}_d$ be the class of $d$-degenerate graphs and let $L$ be a list assignment for a graph $G$. A colouring of $G$ such that every vertex receives a colour from its list and the subgraph induced by vertices coloured with one color is a $d$-degenerate graph is called the $(L,{\mathcal D}_d)$-colouring of $G$. For a $k$-uniform list assignment $L$ and $d\in\mathbb{N}_0$, a graph $G$ is equitably $(L,{\mathcal D}_d)$-colorable if there is an $(L,{\mathcal D}_d)$-colouring of $G$ such that the size of any colour class does not exceed $\left\lceil|V(G)|/k\right\rceil$. An equitable $(L,{\mathcal D}_d)$-colouring is a generalization of an equitable list coloring, introduced by Kostochka at al., and an equitable list arboricity presented by Zhang. Such a model can be useful in the network decomposition where some structural properties on subnets are imposed. In this paper we give a polynomial-time algorithm that for a given $(k,d)$-partition of $G$ with a $t$-uniform list assignment $L$ and $t\geq k$, returns its equitable $(L,\mathcal{D}_{d-1})$-colouring. In addition, we show that 3-dimensional grids are equitably $(L,\mathcal{D}_1)$-colorable for any $t$-uniform list assignment $L$ where $t\geq 3$.
