Coloring vertices and faces of maps on surfaces

DOI10.1016/J.DISC.2010.06.021MaRDI QIDQ708418zbMATH OpenOpenAlexFDO

Authors Vladimir P. Korzhik

Publication date 11 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2010.06.021

zbMATH Keywords

1-immersion of graphnonorientable surfaceone-chromatic numbertopological embeddingvertex-face chromatic number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Review text

\textit{A map on a surface} is a cellular embedding of a graph (possibly with loops and multiedges) in the surface. The vertex-face chromatic number \(\chi_{vf} (M)\) of a map \(M\) on a surface is the minimum integer \(m\) such that the vertices and faces of \(M\) can be coloured by \(m\) colours in such a way that adjacent or incident elements receive distinct colours. The vertex-face chromatic number \(\chi_{vf} (S)\) of a surface \(S\) is the maximal value of \(\chi_{vf} (M)\) taken over all maps \(M\) on \(S\). The author provides an upper on \(\chi_{vf} (S)\) for the surfaces of Euler genus \(\geq 2\). The upper bound is less (by 1) than Ringel's upper bound on the 1-chromatic number of a surface for about 5/12 of all surfaces (see [\textit{G. Ringel}, ``A nine color theorem for the torus and the Klein bottle, The theory and applications of graphs, 4th int. Conf., Kalamazoo/Mich. 1980, 507--515 (1981; Zbl 0469.05031)]). The author presents some arguments that indicate that the upper bound on the vertex-face chromatic number is tight.

Recommendations

• scientific article; zbMATH DE number 4108786
• Colouring graphs on surfaces
• Colouring graphs on surfaces
• Coloring face hypergraphs on surfaces
• Coloring face-hypergraphs of graphs on surfaces
• Coloring parameters for graphs on surfaces
• Coloring triangle-free graphs on surfaces
• Coloring Triangle-Free Graphs on Surfaces
• Coloring vertices and faces of locally planar graphs
• On colorings of maps

Cites work

• A lower bound for the one-chromatic number of a surface
• A possibly infinite series of surfaces with known 1-chromatic number
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• An infinite series of surfaces with known 1-chromatic number
• Coloring vertices and faces of locally planar graphs
• Ein 7-Farbensatz 1-einbettbarer Graphen auf der projektiven Ebene
• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• scientific article; zbMATH DE number 4089570 (Why is no real title available?)
• scientific article; zbMATH DE number 3735846 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• Map-Colour Theorems
• The nonorientable genus of joins of complete graphs with large edgeless graphs
• The number of edges in critical graphs.

Cited in

(5)

• A possibly infinite series of surfaces with known 1-chromatic number
• Acyclic \(k\)-strong coloring of maps on surfaces
• On the face touching number
• Coloring parameters for graphs on surfaces
• The vertex-face chromatic number of almost all nonorientable surfaces

This page was built for publication: Coloring vertices and faces of maps on surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q708418)