4-chromatic edge critical Grötzsch–Sachs graphs
| Autor: | Leonid S. Mel'nikov, Andrey A. Dobrynin |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
Grötzsch–Sachs graphs Symmetric graph Chromatic number Planar graphs Vertex coloring 4-critical graphs 1-planar graph Planar graph Theoretical Computer Science Combinatorics symbols.namesake Pathwidth Dual graph Chordal graph symbols Discrete Mathematics and Combinatorics Cycle decomposition Graph coloring Mathematics |
| Zdroj: | Discrete Mathematics. 309(8):2564-2566 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2008.06.006 |
| Popis: | Let G be a 4-regular plane graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly one cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such a graph G arises as a superposition of simple closed curves in the plane with tangencies disallowed. Two 4-chromatic edge critical graphs of order 48 generated by four curves are presented. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect