On vertex orderings and the stability number in triangle-free graphs (Q5937606): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(00)00335-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2073631490 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:06, 30 July 2024
scientific article; zbMATH DE number 1619857
Language | Label | Description | Also known as |
---|---|---|---|
English | On vertex orderings and the stability number in triangle-free graphs |
scientific article; zbMATH DE number 1619857 |
Statements
On vertex orderings and the stability number in triangle-free graphs (English)
0 references
21 April 2002
0 references
Let \(G= G(V,E)\) be a simple and finite graph. A set \(S\) of pairwise non-adajcent vertices in \(G\) is called stable. \(S\) is a maximal stable set in \(G\), if \(G\) has no stable \(S'\) with \(S\subset S'\), and the cardinality of such an \(S\) is called the stability number \(\alpha(G)\) of \(G\). A maximal stable set of \(G\) can be got by applying a certain algorithm, called greedy algorithm, on a given ordering \(v_1,\dots, v_n\) of the vertices of \(G\). For this algorithm the vertices in the given order are to scan and \(v_i\) is to put in \(S\) only if no vertex \(v_j\) in \(S\) with \(j< i\) is adjacent to it. The cardinality of the stable set that arises in this way is denoted by \(\alpha(G; v_1,\dots, v_n)\). If \(\alpha(G)= \alpha(G; v_1,\dots, v_n)\) then the ordering \(v_1,\dots, v_n\) is called an \(\alpha\)-ordering and it is known that the determination of an \(\alpha\)-ordering of a graph \(G\) is NP-hard. \textit{N. V. R. Mahadev} and \textit{B. A. Reed} [J. Graph Theory 30, No. 2, 113-120 (1999; Zbl 0918.05086)] investigated two types of vertex orderings satisfying certain conditions (Property 1 and Property 2) and they characterized a class of graphs for which a maximum stable set can be computed in polynomial time. The author gives a partial answer to a further question of Mahadev and Reed and he gives a complete characterization of all triangle-free graphs that have Property 2 (for every induced subgraph \(H\) of \(G\), every ordering of the vertices of \(H\) that is of the above shortly indicated Type 2 is an \(\alpha\)-ordering) in terms of an infinite number of forbidden induced subgraphs; here a maximal stable set also can be computed in polynomial time. Three classes \({\mathfrak C}_1\), \({\mathfrak C}_2\) and \({\mathfrak C}_3\) of graphs which contain these forbidden induced subgraphs are defined. \({\mathfrak C}_1\cup {\mathfrak C}_2\cup{\mathfrak C}_3\) is denoted by \({\mathfrak C}\). The following main result is proved: A triangle-free graph \(G\) has Property 2 iff it contains no graph in \({\mathfrak C}\) as an induced subgraph (Theorem 1). The proof of this theorem is given by proving a more extensive structural result (Theorem 2) which implies Theorem 1.
0 references
maximal stable set
0 references
stability number
0 references
greedy algorithm
0 references
characterization
0 references
triangle-free graphs
0 references
forbidden induced subgraphs
0 references