No label defined (Q3737449)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3970775
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3970775

      Statements

      1985
      0 references
      4-regular planar graphs
      0 references
      colorings
      0 references
      [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.
      0 references
      0 references

      Identifiers