scientific article; zbMATH DE number 3970775

From MaRDI portal
Publication:3737449





[For the entire collection see Zbl 0588.00010.] Let \({\mathfrak G}\) denote the class of all 4-regular planar graphs generated by the transversal intersection of simple closed curves. Let \({\mathfrak G}_ k\) denote the graphs in \({\mathfrak G}\) where these curves can be partitioned into k classes such that any two curves in the same class do not intersect. The author disproves a conjecture by H. Grotzsch by giving a \(G\in {\mathfrak G}\) with \(\chi (G)=4\) where \(\chi\) is the vertex chromatic number of a graph. He proves that the maximum chromatic number for \(G\in {\mathfrak G}_ 2\) is 2, this maximum for \({\mathfrak G}_ 3\) is 3, and for \({\mathfrak G}_ k\), \(k\geq 5\) is 4. He conjectures that this maximum for \({\mathfrak G}_ 4\) is 3. A second part of this paper gives an example of a planar graph which is 4-critical with respect to vertex colorings and has 2n edges. T. Gallai had conjectured that any such graph had at most 2n-2 edges. The final part of the paper considers edge colorings of graphs in \({\mathfrak G}\). F. Jaeger has conjectured that every \(G\in {\mathfrak G}\) is 4-edge- colorable. The author proves that this conjecture is true for graphs in \({\mathfrak G}_ 3\). He also presents a necessary condition for an n-regular graph to be n-edge-colorable. This condition is the same as Seymour's r- graph.




Cited in
(29)








This page was built for publication:

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