کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427035 | 686427 | 2016 | 8 صفحه PDF | دانلود رایگان |
• The problem of deciding whether a triangulation is acyclically 4-colorable is NP-complete.
• Every acyclically 4-colorable triangulation with minimum degree more than 3 contains at least four odd-vertices.
• For every acyclic 4-colorable 4-connected triangulation with exactly four odd-vertices, it follows that the subgraph induced by the four odd-vertices is triangle-free and claw-free.
An acyclic k-coloring of a graph is a proper vertex k-coloring such that every bichromatic subgraph, induced by this coloring, contains no cycles. A graph is acyclically k-colorable if it has an acyclic k-coloring. In this paper, we prove that every acyclically 4-colorable triangulation with minimum degree more than 3 contains at least four odd-vertices. Moreover, we show that for an acyclically 4-colorable triangulation with minimum degree 4, if it contains exactly four odd-vertices, then the subgraph induced by its four odd-vertices is triangle-free and claw-free.
Journal: Information Processing Letters - Volume 116, Issue 6, June 2016, Pages 401–408