Polychromatic coloring of triangular-face-free plane graphs

DOI10.1016/J.DISC.2026.115187MaRDI QIDQ7285278zbMATH OpenFDO

Authors Alkajim Ahadi Aradais, Ferdinand P. Jamil, Naoki Matsumoto, Atsuhiro Nakamoto, Kyosuke Wakayama

Publication date 19 June 2026

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2026.115187

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Review text

This paper studies proper polychromatic colorings of plane graphs. For a plane graph \(G\), an \(m\)-polychromatic \(k\)-coloring is defined as a proper \(k\)-coloring such that every facial closed walk contains at least \(m\) distinct colors. The authors focus on the case \(m=4\) for triangular-face-free plane graphs.\N\NThe main result states that every triangular-face-free subcubic plane graph admits a \(4\)-polychromatic \(5\)-coloring, and that the bound \(5\) is best possible. The paper also proves that every triangular-face-free plane graph admits a \(4\)-polychromatic \(6\)-coloring, again with the best possible bound. The proof for the \(3\)-edge-connected case uses reductions on dual triangulations via edge contractions and octahedron removals, while the remaining cases are handled by inductive decomposition and recoloring arguments.

Cites work

• 3-polychromatic quadrangulations on surfaces
• \(K_7\)-minors in optimal 1-planar graphs
• A combinatorial theorem in plane geometry
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• A short proof of Chvatal's Watchman Theorem
• Cyclic 4-colorings of graphs on surfaces
• Ein Sechsfarbenproblem auf der Kugel
• Extension to 3-colorable triangulations
• Facially-constrained colorings of plane graphs: a survey
• Full 4-colorings of 4-regular maps
• Generating even triangulations on the Klein bottle
• Generating even triangulations on the torus
• Generating triangulations on closed surfaces with minimum degree at least 4
• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• Inductive definition of two restricted classes of triangulations
• Polychromatic 4-coloring of cubic bipartite plane graphs
• Polychromatic 4-coloring of cubic even embeddings on the projective plane
• Polychromatic colorings of bounded degree plane graphs
• Polychromatic colorings of plane graphs
• Vorlesungen über die Theorie der Polyeder unter Einschluß\ der Elemente der Topologie.

This page was built for publication: Polychromatic coloring of triangular-face-free plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7285278)