TOPICS
Search

Clar and Fries Numbers


A face of a plane bipartite graph is alternating with respect to a perfect matching if its boundary is a cycle whose edges alternate between matched and unmatched edges. The Fries number is the maximum number of alternating bounded faces over all perfect matchings. The Clar number is the maximum number of pairwise vertex-disjoint alternating bounded faces for a single perfect matching (Bérczi-Kovács and Frank 2024).

Orden (2026) reports a counterexample to the claim that every maximum Clar set is contained in the alternating faces of a Fries-optimal perfect matching. In the grid graph of an 11-square polyomino, the unique Fries-optimal perfect matching has eight alternating faces, of which at most four are pairwise vertex-disjoint. The Clar number is five. Two enumerations written by Claude agents checked all 116 perfect matchings, and the author provides a public checker. The work is under journal review. The example uses square faces, leaving the corresponding question for benzenoids open.


See also

Bipartite Graph, Perfect Matching

Explore with Wolfram|Alpha

References

Bérczi-Kovács, K. and Frank, A. "A Network Flow Approach to a Common Generalization of Clar and Fries Numbers." Disc. Math. 347, 114145, 2024. https://doi.org/10.1016/j.disc.2024.114145.Orden, T. S. "Clar and Fries Counterexample and Checker." 2026. https://doi.org/10.5281/zenodo.24064869.

Cite this as:

Weisstein, Eric W. "Clar and Fries Numbers." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ClarandFriesNumbers.html

Subject classifications