偶著色問題之探討

Abstract

給定一個無向圖G，如果著色φ對所有頂點v皆存在一顏色c使得N(v)內顏色為c的個數為正偶數，則著色φ為偶著色。對於任意正整數k，k-偶著色問題為是否存在一k-著色為偶著色。關於2-偶著色問題，我們提出此問題在二分圖上是NP完備問題。在conflict-free著色問題上，Bhyravarapu等人在Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs中提出使用團寬與顏色數作為參數的固定參數可解演算法。延伸他們的想法，我們提出了在2-偶著色問題上使用秩寬作為參數的固定參數可解演算法。對於conflict-free 著色問題，我們給出了在有支配點對的二分圖上conflict-free著色問題色數的上界。Given an undirected graph G, a coloring φ of G is said to be even if for each vertex v ∈ V (G) there exists a color c such that φ−1(c)∩N(v) is positive even-size. For an integer k, the even k-coloring problem asks whether an input graph admits an even k-coloring. We show that for any bipartite graph, the even 2-coloring problem is NP-complete. In [Bhyravarapu et al., Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs, in IWOCA, 2021], they gave a fixedparameter tractable algorithm parameterized by clique-width and number of colors as the parameter to decide whether the coloring is conflict-free. Extending their idea, we give an FPT algorithm with rank-width as the parameter to decide whether there exist an even 2-coloring. For conflict-free coloring, we give an upper bound on the conflict-free chromatic number of weak dominating pair bipartite graphs.