Mock threshold graphs

被引：4

作者：

Behr, Richard ^{[1
]}

Sivaraman, Vaidy ^{[1
]}

Zaslaysky, Thomas ^{[1
]}

机构：

[1] SUNY Binghamton, Dept Math Sci, Binghamton, NY 13902 USA

来源：

DISCRETE MATHEMATICS | 2018年 / 341卷 / 08期

关键词：

Mock threshold graph; Perfect graph; Forbidden induced subgraph; Claw-free graph; Line graph; Chordal graph;

D O I：

10.1016/j.disc.2018.04.023

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold graphs by forbidden induced subgraphs. Other theorems characterize mock threshold graphs that are claw-free and that are line graphs. We also discuss relations with chordality and well-quasi-ordering as well as algorithmic aspects. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：2159 / 2178

页数：20

共 14 条

[1]

[Anonymous], 1973, 7321 CORR

[2]

[Anonymous], 1977, P 8 S E C COMB GRAPH

[3]

Beineke L.W., 1970, J. Combin. Th. Ser B, V9, P129

[4] The strong perfect graph theorem [J].

Chudnovsky, Maria ;

Robertson, Neil ;

Seymour, Paul ;

Thomas, Robin .

ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229

[5] Upper bounds to the clique width of graphs [J].

Courcelle, B ;

Olariu, S .

DISCRETE APPLIED MATHEMATICS, 2000, 101 (1-3) :77-114

[6]

Dirac G.A., 1961, Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]

[7] Claw-free graphs - A survey [J].

Faudree, R ;

Flandrin, E ;

Ryjacek, Z .

DISCRETE MATHEMATICS, 1997, 164 (1-3) :87-147

[8] COMPLEXITY RESULTS FOR BANDWIDTH MINIMIZATION [J].

GAREY, MR ;

GRAHAM, RL ;

JOHNSON, DS ;

KNUTH, DE .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1978, 34 (03) :477-495

[9] HAMILTONIAN THRESHOLD GRAPHS [J].

HARARY, F ;

PELED, U .

DISCRETE APPLIED MATHEMATICS, 1987, 16 (01) :11-15

[10] WEAKLY TRIANGULATED GRAPHS [J].

HAYWARD, RB .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (03) :200-209

← 1 2 →