Planar graphs without short even cycles are near-bipartite
| Autor: | Runrun Liu, Gexin Yu |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
Mathematics::Combinatorics Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Planar graph Combinatorics symbols.namesake Computer Science::Discrete Mathematics 010201 computation theory & mathematics Independent set Bipartite graph symbols Discrete Mathematics and Combinatorics Mathematics |
| Zdroj: | Discrete Applied Mathematics. 284:626-630 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2020.04.017 |
| Popis: | A graph is near-bipartite if its vertex set can be partitioned into an independent set and a set that induces a forest. It is clear that near-bipartite graphs are 3-colorable. In this note, we show that planar graphs without cycles of lengths in { 4 , 6 , 8 } are near-bipartite. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect