Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

O. V. Borodin, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review

Abstract

A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V1and V0so that in G[V1] every vertex has degree at most 1, while G[V0] is edgeless. We prove that every graph with maximum average degree at most 12/5 is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to 12/5 which are not (1, 0)-colorable. In fact, we prove a stronger result by establishing the best possible sufficient condition for the (1, 0)-colorability of a graph G in terms of the minimum, Ms(G), of 6|V (A)| − 5|E(A)| over all subgraphs A of G. Namely, every graph G with Ms(G) ≥ −2 is proved to be (1, 0)-colorable, and we construct an infinite series of non-(1, 0)-colorable graphs G with Ms(G) = −3.

Original languageEnglish (US)
Pages (from-to)796-801
Number of pages6
JournalSiberian Mathematical Journal
Volume52
Issue number5
DOIs
StatePublished - 2011

Keywords

  • Coloring
  • Girth
  • Planar graphs

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1'. Together they form a unique fingerprint.

Cite this