Browsing by Author "饒旻書"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    偶著色問題之探討
    (2024) 饒旻書; Jao, Min-Shu
    給定一個無向圖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著色問題色數的上界。