The complexity of some acyclic improper colourings |
| |
Authors: | Mieczys?aw Borowiecki Katarzyna Jesse-Józefczyk El?bieta Sidorowicz |
| |
Institution: | University of Zielona Góra, Faculty of Mathematics, Computer Science and Econometrics, ul. prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland |
| |
Abstract: | In this paper we will consider acyclic bipartition of the vertices of graphs, where acyclic means that the edges whose endpoints are in different parts of the partition induce a forest. We will require that the vertices belonging to the same partition induce graphs from particular class. We will search for acyclic bipartitions of cubic and subcubic graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|