Triangle-free planar graphs with small independence number

Autor:	Dvořák, Zdeněk, Venters, Jordan
Rok vydání:	2017
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C69 (Primary) 05C85 (Secondary) G.2.2
Druh dokumentu:	Working Paper
Popis:	Since planar triangle-free graphs are 3-colourable, such a graph with n vertices has an independent set of size at least n/3. We prove that unless the graph contains a certain obstruction, its independence number is at least n/(3-epsilon) for some fixed epsilon>0. We also provide a reduction rule for this obstruction, which enables us to transform any plane triangle-free graph G into a plane triangle-free graph G' such that alpha(G')-|G'|/3=alpha(G)-|G|/3 and |G'|<=(alpha(G)-|G|/3)/epsilon. We derive a number of algorithmic consequences as well as a structural description of n-vertex plane triangle-free graphs whose independence number is close to n/3. Comment: 24 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1702.02888 Zobrazit plný text záznamu View this record from Arxiv