給定一個無向圖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.

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.
Zhengke Miao, Lin Sun, Zhuojie Tu, Xiaowei Yu, On odd colorings of planar graphs, Discrete Math., vol. 347, no. 1, Jan 2024.
T. J. Schaefer, The complexity of satisfiability problems, STOC '78: Proceedings of the tenth annual ACM symposium on Theory of computing, San Diego California, USA, pp. 216–226, May 1978.
C. Moore, S. Mertens, Symmetry-breaking and NAESAT, The Nature of Computation, Oxford University Press, pp. 133–138, ISBN 9780199233212
B. Courcelle, and S. Olariu. Upper bounds to the clique width of graphs, Discrete Appl. Math., vol. 101, pp. 77–114, 2000.
S. Oum, and P. Seymour, Approximating clique-width and branch-width, J. Comb. Theory, Series B, vol. 96, no. 4, pp. 514-528, Jul 2006.
S. Oum, Rank-width: Algorithmic and structural results, Discrete Appl. Math., vol. 231, pp. 15-24, Nov 2017.
S. Oum, Rank-width and vertex-minors, J. Comb. Theory, Series B, vol. 95, no. 1, pp. 79-100, Sep 2005.
J. Ahn, S. Im, and S. Oum, The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs, SSRN: https://ssrn.com/abstract=4334389
M. Petruševski, and R. Škrekovski, Colorings with neighborhood parity condition, Discrete Appl. Math., vol. 321, pp. 385-391, Nov 2022.
J. S. Deogun, and D. Kratsch, Dominating Pair Graphs, SIAM J. Discrete Math., vol. 15, no. 3, pp. 353-366, 2002.
L. Alcón, A Note on Path Domination, Discuss. Math. Graph Theory, vol. 36, no. 4, pp. 1021-1034, 2016.
L. Gargano, and A. A. Rescigno, Complexity of conflict-free colorings of graphs, Theor. Comput. Sci., vol. 566, pp. 39-49, Feb 2015.
S. P. Fekete, and P. Keldenich, Conflict-free coloring of intersection graphs, Int. J. Comput. Geom. Appl., vol. 28, no. 3, pp. 289-307, 2018.
J. PACH, and G. TARDOS, Conflict-Free Colourings of Graphs and Hypergraphs, Comb. Probab. Comput., vol. 18, no. 5, pp. 819–834, 2009. doi:10.1017/S0963548309990290
P. Erdős, and L. Lovász, Problems and results on 3-chromatic Hypergraphs and some related questions, Coll Math Soc J Bolyai. vol. 10, pp. 609-627, 1975.
S. Bhyravarapu, S. Kalyanasundaram, and R. Mathew, Conflict-Free Coloring Bounds on Open Neighborhoods, Algorithmica vol. 84, pp. 2154–2185, 2022. \url{https://doi.org/10.1007/s00453-022-00956-6}
S. Bhyravarapu, S. Kalyanasundaram, R. Mathew, Conflict-Free Coloring Bounds on Open Neighborhoods, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, Leibniz International Proceedings in Informatics (LIPIcs), vol. 241, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)