A note of vertex arboricity of planar graphs without 4-cycles intersecting with 6-cycles
| Autor: | Xing Liu, Huijuan Wang, Wenshun Teng, Xuyang Cui |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
General Computer Science Arboricity 0102 computer and information sciences 02 engineering and technology Directed acyclic graph 01 natural sciences Theoretical Computer Science Planar graph Combinatorics symbols.namesake Computer Science::Discrete Mathematics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering symbols Partition (number theory) 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | Theoretical Computer Science. 836:53-58 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2020.06.009 |
| Popis: | The vertex arboricity v a ( G ) of G is the smallest integer k which the acyclic partition of V ( G ) make the vertex set V ( G ) be partitioned into k subsets which each subset induces an acyclic graph. In this paper, we mainly study vertex arboricity of planar graphs, and we prove that if there is without 4-cycles intersecting with 6-cycles, then v a ( G ) ⩽ 2 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect