偶著色問題之探討

A study on the even coloring of a graph

饒旻書(Jao Min-Shu)

指導教授 ： 王弘倫

國立臺灣師範大學/理學院/資訊工程學系/碩士(2024年)

https://doi.org/10.6345/NTNU202401491

摘要

給定一個無向圖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著色問題色數的上界。

關鍵字

偶著色問題 ； 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.

並列關鍵字

Even coloring ； Conflict-free coloring ； FPT algorithm ； Rank-width

參考文獻

G. Even, Z. Lotker, D. Ron, and S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM J. Comput., vol. 33, no. 1, pp. 94-136, Feb 2003.

S. Bhyravarapu, S. Kalyanasundaram, and R. Mathew, A short note on conflict‐free coloring on closed neighborhoods of bounded degree graphs, J. Graph Theory., vol. 97, no. 4, pp. 553-556, Jul 2021.

Z. Abel, V. Alvarez, E. D. Demaine, S. P. Fekete, A. Gour, A. Hesterberg, P. Keldenich, and C. Scheffer, Conflict-Free Coloring of Graphs, SIAM J. DISCRETE MATH., vol. 32, no. 4, pp. 2675-2702, 2018.

S. Bhyravarapu, T. A. Hartmann, S. Kalyanasundaram, and I. V. Reddy, Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs, in IWOCA, Ottawa, ON, Canada, 2021, pp. 92-106.

Y. Caro, M. Petruševski, and R. Škrekovski, Remarks on odd colorings of graphs, Discrete Appl. Math., vol. 321, pp. 392-401, Nov 2022.