On the Classical and Parameterized Complexity of Strong Odd Coloring

1 Introduction

• Strong odd coloring requires every color in each non-isolated vertex’s neighborhood to occur an odd number of times, so χ(G) ≤ χo(G) ≤ χso(G) ≤ χ(G2).Odd coloring requires only that at least one neighborhood color occur an odd number of times; strong odd coloring is the stricter version introduced by Kwon and Park.Source: §1 · p. 1
• The strong odd chromatic number can differ arbitrarily from both the odd chromatic number and the chromatic number of the graph square.For complete bipartite graphs, the square’s chromatic number is m+n while the strong odd chromatic number is at most 4; the paper also gives examples separating strong odd and odd chromatic numbers.Source: §1 · p. 2
• The paper addresses a gap in computational study: prior work focused mainly on structural bounds and strong odd chromatic numbers for specific graph classes.Prior work had established bounds for planar graphs and minor-closed and bounded-expansion classes.Source: §1 · p. 2
• Strong odd k-colorability was already known to be NP-complete for k ≥ 3, while linear-time algorithms were known for trees and unicyclic graphs.The paper studies classical complexity and initiates the parameterized-complexity study of the problem.Source: §1 · p. 2
• Strong odd k-colorability is NP-complete on bipartite graphs for k ≥ 3, and the strong odd chromatic number is inapproximable within O(n^(1/2−ε)) for every ε > 0 unless P = NP.The paper establishes the hardness result in particular for perfect elimination bipartite graphs, a subclass of bipartite graphs.Source: §1 · p. 2
• A linear-time algorithm computes an optimal strong odd coloring of block graphs by traversing their cut-tree and reusing colors from a parent cut vertex.The algorithm uses breadth-first traversal and recursively colors the block children of each cut vertex.Source: §1 · p. 2
• For treewidth, the paper gives an FPT algorithm and proves under SETH that no (k−ε)^tw n^O(1)-time algorithm exists for k ≥ 3 and ε > 0.The algorithm runs in O((k · 9k)^(tw+1) · n^O(1)) time; whether this can be improved to narrow the gap with the lower bound remains open.Source: §1 · p. 2
• Strong odd k-colorability has no polynomial kernel parameterized by feedback vertex set and is W[1]-hard parameterized by clique-width.Source: §1 · p. 2

2 Preliminaries

• A coloring satisfies the strong odd condition at a vertex when every color appearing in its neighborhood occurs there an odd number of times.The paper considers finite, connected, simple, undirected graphs.Source: §2 · p. 3
• A bipartite graph is a perfect elimination bipartite graph if it has an edge ordering in which each successive edge is bisimplicial after earlier edge endpoints are removed.An edge is bisimplicial when the subgraph induced by the neighborhoods of its endpoints is complete bipartite.Source: §2 · p. 3
• A block graph is a graph in which every block—a maximal connected subgraph without a cut vertex—is a clique.Source: §2 · p. 3
• A tree decomposition uses vertex-set bags covering vertices and edges, with the bags containing any given vertex forming a connected subtree; its width is the largest bag size minus one.The graph’s treewidth is the minimum width over its tree decompositions.Source: §2 · p. 3
• A nice tree decomposition has singleton root and leaf bags, with each non-leaf node an introduce, forget, or join node.A width-k tree decomposition can be converted to a nice one of width at most k with O(k|V(G)|) nodes.Source: §2 · p. 3
• A feedback vertex set leaves a forest when removed; clique-width is the fewest labels needed to construct a graph using vertex introduction, disjoint union, edge introduction, and label renaming.A polynomial kernel bounds the size of an equivalent instance by a polynomial in the parameter; FPT means solvable in g(d)|x|^O(1) time for a computable function g.Source: §2 · pp. 3–4

3 Hardness results

• The strong odd chromatic number is inapproximable within O(n^(1/2−ε)) for every ε > 0.The reduction uses a constructed graph H with χso(H) ≤ χ(G) + 2 to transfer approximation to ordinary chromatic number.Source: §3 · pp. 4–7
• Strong odd k-colorability is NP-complete on perfect elimination bipartite graphs for every k ≥ 3.The reduction preserves k-colorability: G is k-colorable if and only if the constructed H is strong odd k-colorable.Source: §3 · pp. 4–5

4 Linear-time algorithm in block graphs

• For a complete graph G, the strong odd chromatic number equals its clique number, χso = ω(G).Source: §4 · p. 7
• A linear-time algorithm computes an optimal strong odd coloring of a block graph by processing an ordered cut-tree rooted at a cut vertex.The cut-tree can be constructed by depth-first search; the algorithm traverses it in breadth-first order and invokes ColorRoot and ColorCutVertex.Source: §4 · pp. 7, 9
• ColorRoot colors the root and its block children so that the root satisfies the strong odd condition.It arranges for colors used in earlier blocks to have even multiplicity in the root’s neighborhood before using them in the final block, making their multiplicity odd.Source: §4 · pp. 8–9
• ColorCutVertex colors all block children of a processed cut vertex so that the vertex satisfies the strong odd condition.The procedure manages color multiplicities across the neighborhood outside the final block before coloring that block.Source: §4 · pp. 9–10
• ColorCutVertex reuses selected colors to make their neighborhood counts even or odd, then uses fresh colors so every other appearing color occurs once.The parity adjustment depends on whether all colors in T are exhausted during processing.Source: §4 · pp. 11–12
• Algorithm 1 produces a proper coloring in which every vertex satisfies the strong odd condition.Vertices outside the cut-vertex set satisfy the condition because each neighborhood is a clique; the algorithm preserves the condition for cut vertices.Source: §4 · pp. 12–13
• At a cut vertex where Algorithm 1 reaches k colors, parity constraints across its incident blocks force every strong odd coloring to use at least k colors.The proof considers both root and non-root cut vertices to establish the lower bound.Source: §4 · pp. 13–14
• Algorithm 1 returns an optimal strong odd coloring of every block graph in O(|V(G)| + |E(G)|) time.The proof establishes optimality through feasibility and a matching lower bound on the number of colors.Source: §4 · p. 14

• A nice-tree-decomposition dynamic program stores bag colorings and 0/odd/even neighborhood-parity states, runs in O(n^O(1) · (k · 9^k)^(tw+1)), and yields an FPT algorithm by treewidth.Source: §5 · pp. 15, 17
• Under SETH, for every k ≥3 and ε > 0, strong odd k-colorability has no (k − ε)^tw n^O(1)-time algorithm.Source: §5 · pp. 17–18
• Parameterized by feedback vertex set, strong odd k-colorability has no polynomial kernel unless NP ⊆ coNP/poly.Source: §5 · p. 18
• Parameterized by clique-width, the problem is W[1]-hard; its reduction from k-Colorability increases clique-width by at most 3.Source: §5 · p. 19