Skip to content
DraconiticResearch
Search Sources API
182,460 studies31 sourcesUpdated 33 min ago
PreprintarXiv licencearXiv

The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs

  • James Alexander Schreib
Open at sourcePDFDOICite

Abstract

We prove the conjecture of Borowiecki and Broere that every finite simple planar graph admits a generalized total coloring with four colors: a proper vertex coloring with four colors together with an edge coloring with four colors in which each edge color class is a forest and no edge receives the color of either endpoint. In fact every proper four-coloring of such a graph extends to an edge coloring of the required kind. The proof combines a component-count inequality for planar graphs whose vertices are partitioned into four independent sets, obtained by completing to a triangulation, with the matroid partition theorem applied to four graphic matroids. A Lean 4 formalization relative to six named background assumptions is described below.

Related

  1. A proof of Wang's planar D-coloring conjecture
    Harshit Verma
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Bounds for B-coloring planar and outerplanar graphs
    Ryan Martin, Miklós Ruszinkó, Gábor Sárközy
    Discrete MathematicsPeer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
  3. Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
    Enqiang Zhu, Yangyang Zhou, Jin Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Bounds for B-coloring planar and outerplanar graphs
    Ryan R. Martin, Miklós Ruszinkó, Gábor N. Sárközy
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Frugal coloring in planar graphs with maximum degree 4 and 5
    Boštjan Brešar, Přemysl Holub, Marko Jakovac +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{schreib2026borowieckibroere,
  title = {{The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs}},
  author = {James Alexander Schreib},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.00091},
  eprint = {2610.00091},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.00091},
}
RIS
TY  - UNPB
TI  - The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
AU  - James Alexander Schreib
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.00091
UR  - https://arxiv.org/abs/2610.00091
AB  - We prove the conjecture of Borowiecki and Broere that every finite simple planar graph admits a generalized total coloring with four colors: a proper vertex coloring with four colors together with an edge coloring with four colors in which each edge color class is a forest and no edge receives the color of either endpoint. In fact every proper four-coloring of such a graph extends to an edge coloring of the required kind. The proof combines a component-count inequality for planar graphs whose vertices are partitioned into four independent sets, obtained by completing to a triangulation, with the matroid partition theorem applied to four graphic matroids. A Lean 4 formalization relative to six named background assumptions is described below.
ER  -