Introduction
In traditional graph theory, a proper coloring ensures that no two adjacent vertices share the same color. This paper explores a more complex variation: the coloring of clique hypergraphs. For a simple graph $G = (V, E)$, the clique hypergraph $CH(G)$ is defined such that its vertices are the same as $G$, but its hyperedges are the maximal cliques of $G$.
A proper $k$-coloring of $CH(G)$ requires that every maximal clique containing at least two vertices is not monochromatic—meaning at least two distinct colors must be present within the clique. This problem is significantly more challenging than standard vertex coloring; for instance, determining if a general perfect graph is bicolorable (2-colorable) is an NP-complete problem. This research identifies specific graph classes where efficient coloring is possible and investigates the conditions under which a partial coloring can be successfully extended.
Bicolorability in Chordal and Comparability Graphs
The research establishes that two major classes of graphs—chordal and comparability graphs—are always 2-colorable.
Chordal Graphs
Chordal graphs are defined by the property that every cycle of length four or more contains a chord. The author leverages the existence of simplicial vertices (vertices whose neighbors form a clique) and Perfect Elimination Schemes (PES) to prove bicolorability. By iteratively removing simplicial vertices, the paper demonstrates an inductive proof for 2-colorability and provides an $O(n+m)$ linear-time algorithm to achieve it.
Comparability Graphs
Comparability graphs are those that admit a transitive orientation. The author provides an elegant structural solution for these graphs: by orienting the edges transitively, one can color all "source" vertices (those with no incoming edges) with one color and all remaining vertices with a second color. Because every maximal clique in a transitively oriented graph contains exactly one source, this method guarantees that no maximal clique is monochromatic.
Circular-Arc Graphs and 3-Colorability
Circular-arc graphs, which represent the intersection of arcs on a circle, present a higher complexity. The paper proves that these graphs are 3-colorable. This bound is shown to be optimal, as odd cycles (which are circular-arc graphs) inherently require three colors to avoid monochromatic maximal cliques.
The proof relies on the relationship between circular-arc and interval graphs. By removing a single vertex and its neighborhood from a circular-arc graph, the remaining structure becomes an interval graph (a subclass of chordal graphs). This reduction allows for the development of an $O(n+m)$ algorithm for 3-coloring.
The Coloring Extension Problem
A significant portion of the paper is dedicated to $(W, s)$-extendibility. This asks whether a pre-existing color assignment on a subset of vertices $W$ using $s$ colors can be extended to a valid $s$-coloring for the entire clique hypergraph.
The main result in this area is a characterization of $(W, 2)$-extendibility for chordal graphs when $|W|=2$. The author identifies "forbidden paths"—specific structural arrangements in chordal graphs that prevent a 2-coloring from being completed based on the parity of the path length between the pre-colored vertices.
Conclusion and Future Directions
This work maps the boundaries of polynomial-time solvability for clique hypergraph coloring. While providing efficient algorithms for chordal, comparability, and circular-arc graphs, it leaves several open questions. Notably, the complexity of determining if a circular-arc graph is 2-colorable remains unknown. Future research may extend these findings to other subclasses of perfect graphs, such as weakly chordal graphs, to further refine our understanding of hypergraph colorability.
Summary updated