Simultaneous coloring of edges and faces of plane graphs (Q1322167): Difference between revisions

The edge-and-face chromatic number \(\chi_{\text{ef}}(G)\) of a plane graph \(G\) is the least number of colors required to color the edges and faces of \(G\) such that every two adjacent or incident of them receive different colors. It is proved that if \(G\) is a plane graph with maximum degree at least 10 then \(\chi_{\text{ef}}(G)\leq \Delta(G)+1\), the bound being sharp. The proof is based on some new generalizations of Kotzig's Theorem on the minimal weight of edges in plane graphs. It is also proved that if \(G\) is a plane graph without separating triangles and \(\Delta(G)\leq 7\) then \(\chi_{\text{ef}}(G)\leq 10\).