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
0.8354620337486267
0 references
0.8321855068206787
0 references
0.823506236076355
0 references
0.8192407488822937
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