Simultaneous coloring of edges and faces of plane graphs (Q1322167): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:56, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Simultaneous coloring of edges and faces of plane graphs |
scientific article |
Statements
Simultaneous coloring of edges and faces of plane graphs (English)
0 references
5 May 1994
0 references
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\).
0 references
simultaneous coloring
0 references
edge-and-face chromatic number
0 references
plane graph
0 references
Kotzig's Theorem
0 references