scientific article; zbMATH DE number 3970775
[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.
- 4-chromatic edge critical Grötzsch-Sachs graphs
- Vermutungen über numerierbare Graphen. (Conjectures on graphs that can be numbered)
- Note to a problem of T. Gallai and G. A. Dirac
- A solution to a colouring problem of P. Erdős
- Regular colorings in regular graphs
- Counterexamples to Grötzsch-Sachs-Koester's conjecture
- 4-chromatic Koester graphs
- The singular edge set of a 4-coloring
- scientific article; zbMATH DE number 5936522 (Why is no real title available?)
- scientific article; zbMATH DE number 5952228 (Why is no real title available?)
- Vertex signatures and edge-4-colorings of 4-regular plane graphs
- Infinite families of 4-chromatic Grötzsch-Sachs graphs
- 3-Regular Non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces
- scientific article; zbMATH DE number 3974976 (Why is no real title available?)
- Polychromatic 4-coloring of cubic bipartite plane graphs
- scientific article; zbMATH DE number 2015222 (Why is no real title available?)
- On some properties of 4‐regular plane graphs
- Edge-colouring seven-regular planar graphs
- Edge-colouring eight-regular planar graphs
- scientific article; zbMATH DE number 1390128 (Why is no real title available?)
- On 4-edge colouring planar bridgeless graphs with large girth
- Colouring Random 4-Regular Graphs
- A new 4-chromatic edge critical Koester graph
- Kempe equivalence of 4‐critical planar graphs
- H-colorings for 4-regular graphs
- A note on \(\bar{X}\)-coloring and \(\hat{A}\)-coloring 4-regular graphs
- Edge 4-critical Koester graph of order 28
- Coloring circle arrangements: new 4-chromatic planar graphs
- A simple algorithm for 4-coloring 3-colorable planar graphs
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)