On simultaneous colorings of embedded graphs
From MaRDI portal
Let a graph \(G\) of maximum degree \(\Delta\) be imbedded in a closed 2-manifold \(S\). The authors use discharging to show that if \(\Delta\) is large relative to the genus of \(S\), then the edge-face chromatic number and vertex-edge-face chromatic number of the imbedding are bounded above by \(\Delta+1\) and \(\Delta+2\), respectively. Both bounds are best possible. Moreover, the vertex-edge chromatic number of the graph is also bounded above by \(\Delta+2\).
Recommendations
- The edge-face coloring of graphs embedded in a surface of characteristic zero
- Edge colorings of graphs embeddable in a surface of low genus
- Edge coloring of embedded graphs with large girth
- The entire chromatic number of graphs embedded on the torus with large maximum degree
- Coloring edges of embedded graphs
Cited in
(10)- The edge-face coloring of graphs embedded in a surface of characteristic zero
- A structural theorem on embedded graphs and its application to colorings
- Embedding finite graphs into graphs colored with infinitely many colors
- On \(d\)-diagonal colorings of embedded graphs of low maximum face size
- Entire coloring of graphs embedded in a surface of nonnegative characteristic
- Simultaneous embedding of colored graphs
- The entire chromatic number of graphs embedded on the torus with large maximum degree
- Simultaneous coloring of vertices and incidences of outerplanar graphs
- Graph color extensions: When Hadwiger's conjecture and embeddings help
- List-edge and list-total colorings of graphs embedded on hyperbolic surfaces
This page was built for publication: On simultaneous colorings of embedded graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1586769)
