Forbidden induced subgraphs. (English) Zbl 1441.05162

Zaslavsky, Thomas

Sinha, Deepa (ed.) et al., International conference on current trends in graph theory and computation, CTGTC-2016, New Delhi, India, September 17–19, 2016. Amsterdam: Elsevier. Electron. Notes Discrete Math. 63, 3-10 (2017).

Summary: In descending generality I survey: five partial orderings of graphs, the induced-subgraph ordering, and examples like perfect, threshold, and mock threshold graphs. The emphasis is on how the induced subgraph ordering differs from other popular orderings and leads to different basic questions.
For the entire collection see [Zbl 1384.05002].

MSC:

05C60	Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C75	Structural characterization of families of graphs
05C17	Perfect graphs

Keywords:

partial ordering of graphs; hereditary class; induced subgraph ordering; perfect graph; mock threshold graph

References:

[1]	Behr, Richard, Vaidy Sivaraman, and Thomas Zaslavsky, Mock threshold graphs, submitted for publication · Zbl 1388.05073
[2]	Chartrand, Gary; Harary, Frank, Planar permutation graphs, Ann. Inst. H. Poincaré Sect. B (N. S.), 3, 433-438 (1967) · Zbl 0162.27605
[3]	Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. Math. (2), 164, 1, 51-229 (2006) · Zbl 1112.05042
[4]	Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina, Recognizing Berge graphs, Combinatorica, 25, 2, 143-186 (2005) · Zbl 1089.05027
[5]	Chvátal, V.; Hammer, P. L., Set-packing and threshold graphs (1973), Univ. Waterloo, Res. Rep. CORR 73-21
[6]	Chvátal, Václav; Hammer, Peter L., Aggregation of inequalities in integer programming, (Studies in Integer Programming. Studies in Integer Programming, Ann. Discrete Math., vol. 1 (1977), North-Holland: North-Holland Amsterdam), 145-162 · Zbl 0384.90091
[7]	Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703
[8]	Kaminśki, Marcin; Raymond, Jean-Florent; Trunck, Théophile, Well-quasi-ordering H-contraction-free graphs, submitted for publication · Zbl 1346.05278
[9]	Murilo; da Silva, V. G.; Vušković, Kristina, Triangulated neighborhoods in even-hole-free graphs, Discrete Math., 307, 1065-1073 (2007) · Zbl 1115.05078
[10]	Vaidy Sivaraman, in preparation.; Vaidy Sivaraman, in preparation.
[11]	Vaidy Sivaraman, Thomas Zaslavsky, Mock threshold graphs: Planarity, in preparation.; Vaidy Sivaraman, Thomas Zaslavsky, Mock threshold graphs: Planarity, in preparation. · Zbl 1388.05073
[12]	Vušković, Kristina, Even-hole-free graphs: A survey, Appl. Anal. Discrete Math., 4, 219-240 (2010) · Zbl 1265.05518