A lower bound for the one-chromatic number of a surface

DOI10.1006/JCTB.1994.1028MaRDI QIDQ1328382zbMATH OpenOpenAlexFDO

Authors Vladimir P. Korzhik

Publication date 10 October 1994

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1994.1028

zbMATH Keywords

chromatic numberEuler characteristicsurfaceupper bound

Mathematics Subject Classification ID

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

Review text

Let \(\chi_ 1(S)\) be the maximum chromatic number for all graphs which can be drawn on a surface \(S\) so that each edge is crossed by no more than one other edge. It is proved that \(F(S)-34\leq\chi_ 1(S)\), where \(F(S)=\lfloor{1\over 2}(9+\sqrt{81-32E(S)})\rfloor\) is Ringel's upper bound for \(\chi_ 1(S)\) and \(E(S)\) is the Euler characteristic of \(S\).

Recommendations

• A tighter bounding interval for the 1-chromatic number of a surface
• Publication:4887821
• On the 1-chromatic number of nonorientable surfaces with large genus
• A possibly infinite series of surfaces with known 1-chromatic number
• On the dichromatic number of surfaces
• On lower bounds for the chromatic number of sphere
• On lower bounds for the chromatic number of spheres
• An infinite series of surfaces with known 1-chromatic number
• k-chromatic number of graphs on surfaces

Cited in

(10)

• A tighter bounding interval for the 1-chromatic number of a surface
• An infinite series of surfaces with known 1-chromatic number
• A possibly infinite series of surfaces with known 1-chromatic number
• Nonadditivity of the 1-genus of a graph
• scientific article; zbMATH DE number 3972882 (Why is no real title available?)
• On the 1-chromatic number of nonorientable surfaces with large genus
• scientific article; zbMATH DE number 913549 (Why is no real title available?)
• k-chromatic number of graphs on surfaces
• The vertex-face chromatic number of almost all nonorientable surfaces
• Coloring vertices and faces of maps on surfaces

This page was built for publication: A lower bound for the one-chromatic number of a surface

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