TOPICS
Search

Chiu Graph


ChiuGraph

The Chiu graph is the 18-vertex, 36-edge quartic planar graph illustrated above. It is one of exactly 17 quartic planar graphs on 18 vertices with chromatic number 4 and fractional chromatic number 3 (Chiu et al. 2024). No quartic graph on at most 17 vertices has both chromatic values, so the 17 have the smallest possible order among quartic graphs with both properties.

While all 17 are vertex-critical graphs of chromatic number 4, meaning that removing any vertex lowers the chromatic number, only the Chiu graph is an edge-critical graph of chromatic number 4, so removing any edge lowers the chromatic number. The Chiu graph's triangular graph faces allow it to serve as a seed for an infinite family. Applying the "crowning operation" (Koester 1990) to any one of them produces a quartic planar edge-critical graph with fractional chromatic number 3. Each application leaves a triangular face available for the next (Chiu et al. 2024).

As a planar graph with chromatic number 4 and fractional chromatic number 3, the Chiu graph is a counterexample to the conjecture of Gimbel et al. (2019) that every planar graph with chromatic number 4 has fractional chromatic number strictly greater than 3.

The Chiu graph is implemented in the Wolfram Language as GraphData["ChiuGraph"].


See also

Chromatic Number, Fractional Chromatic Number, Johnson Skeleton Graph, Planar Graph, Quartic Graph

Explore with Wolfram|Alpha

References

Chiu, M.-K.; Felsner, S.; Scheucher, M.; Schröder, F.; Steiner, R.; and Vogtenhuber, B. "Coloring Circle Arrangements: New 4-Chromatic Planar Graphs." European J. Combin. 121, 103839, 2024. https://doi.org/10.1016/j.ejc.2023.103839.Gimbel, J.; Kündgen, A.; Li, B.; and Thomassen, C. "Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces." SIAM J. Disc. Math. 33, 1415-1430, 2019. https://doi.org/10.1137/18M1177317.House of Graphs. "Chiu Graph." https://houseofgraphs.org/graphs/51354.Koester, G. "4-Critical 4-Valent Planar Graphs Constructed with Crowns." Math. Scand. 67, 15-22, 1990. https://doi.org/10.7146/math.scand.a-12316.

Cite this as:

Weisstein, Eric W. "Chiu Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ChiuGraph.html

Subject classifications