Proper edge colorings of planar graphs with rainbow C4 ${C}_{4}$‐s
Abstract We call a proper edge coloring of a graph a B‐coloring if every 4‐cycle of is colored with four different colors. Let denote the smallest number of colors needed for a B‐coloring of . Motivated by earlier papers on B‐colorings, here we consider for planar and outerplanar graphs in terms of the maximum degree . We prove that for planar graphs, for bipartite planar graphs, and for outerplanar graphs with . We conjecture that, for sufficiently large, for planar , and for outerplanar .
Authors
- Miklós Ruszinkó (ORCID: https://orcid.org/0000-0003-1664-7717)
- Ryan R. Martin (ORCID: https://orcid.org/0000-0003-0683-1414)
- Gábor N. Sárközy
- András Gyárfás (ORCID: https://orcid.org/0000-0003-1186-7921)
Institutions
- Worcester Polytechnic Institute (US)
- HUN-REN Alfréd Rényi Institute of Mathematics (HU)
- Iowa State University (US)
- Pázmány Péter Catholic University (HU)
- Sorbonne University Abu Dhabi (AE)
Publication Details
- Journal
- Journal of Graph Theory
- Published
- 2024-08-05
- DOI
- https://doi.org/10.1002/jgt.23163
- Citations
- 1
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.36
Funders
- Simons Foundation
- Iowa State University
- Magyar Tudományos Akadémia
- Nemzeti Kutatási Fejlesztési és Innovációs Hivatal