Finding Independent Sets in Triangle-Free Graphs

Autor:	Kathryn Fraughnaugh, Stephen C. Locke
Rok vydání:	1996
Předmět:	Combinatorics Discrete mathematics Matching (graph theory) Chordal graph General Mathematics Independent set Triangle-free graph Cycle graph Maximal independent set Cograph Split graph Mathematics
Zdroj:	SIAM Journal on Discrete Mathematics. 9:674-681
ISSN:	1095-7146 0895-4801
DOI:	10.1137/s0895480194266434
Popis:	Finding a maximum independent set in a graph is well known to be an $NP$-complete problem. Here an $O(n^2)$-time algorithm that finds an independent set of order at least $(6n-m)/13$ in a triangle-free graph with $n$ vertices and $m$ edges is presented. A tight lower bound on independence in 4-regular triangle-free graphs is $4n/13$, so the bound is sharp for this class.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::1e98ab64198f259843d849040f731dfc https://doi.org/10.1137/s0895480194266434 Zobrazit plný text záznamu