Return to search

On Minimal Non-(2, 1)-Colorable Graphs

A graph is (2, 1)-colorable if it allows a partition of its vertices into two classes such that both induce graphs with maximum degree at most one. A non-(2, 1)-colorable graph is minimal if all proper subgraphs are (2, 1)-colorable. We prove that such graphs are 2-edge-connected and that every edge sits in an odd cycle. Furthermore, we show properties of edge cuts and particular graphs which are no induced subgraphs. We demonstrate that there are infinitely many minimal non-(2, 1)-colorable graphs, at least one of order n for all n ≥ 5. Moreover, we present all minimal non-(2, 1)- colorable graphs of order at most seven. We consider the maximum degree of minimal non-(2, 1)-colorable graphs and show that it is at least four but can be arbitrarily large. We prove that the average degree is greater than 8/3 and give sufficient properties for graphs with average degree greater than 14/5. We conjecture that all minimal non-(2, 1)-colorable graphs fulfill these properties.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:su-143532
Date January 2017
CreatorsBosse, Ruth
PublisherStockholms universitet, Matematiska institutionen, -
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0025 seconds