Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949615 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
We prove that if G is a connected graph such with the independence number at most ân2â and the degree sum of any pair of non-adjacent vertices is at least nâ3, then G is on-line arbitrarily partitionable except for two graphs of small orders. We also prove that if G is a connected graph of order n and size âGâ>nâ32+6, then G is on-line AP unless n is even and G is a spanning subgraph of a unique exceptional graph. These two results imply that dense AP graphs satisfying one of the above two assumptions are also on-line AP. This is in contrast to sparse graphs where only few AP graphs are also on-line AP.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
RafaÅ Kalinowski,