20:
23:
A line perfect graph. The edges in each biconnected component are colored black if the component is bipartite, blue if the component is a tetrahedron, and red if the component is a book of triangles.
89:. Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect. By similar reasoning, every line perfect graph is a
262:
287:
Graph-Theoretic
Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings
195:
36:
98:
318:
159:
359:
236:
55:
109:
240:
232:
75:
129:
104:
Line perfect graphs generalize the bipartite graphs, and share with them the properties that the
258:
244:
327:
290:
250:
204:
168:
133:
105:
339:
302:
272:
218:
180:
335:
298:
268:
214:
176:
113:
59:
289:, Lecture Notes in Computer Science, vol. 2204, Berlin: Springer, pp. 317–327,
117:
63:
353:
249:, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin,
209:
94:
44:
90:
48:
28:
19:
285:
Wagler, Annegret (2001), "Critical and anticritical edges in perfect graphs",
254:
40:
294:
331:
172:
18:
47:. Equivalently, these are the graphs in which every odd-length
193:
Maffray, Frédéric (1992), "Kernels in perfect line-graphs",
246:
Geometric algorithms and combinatorial optimization
54:A graph is line perfect if and only if each of its
157:Trotter, L. E. Jr. (1977), "Line perfect graphs",
316:de Werra, D. (1978), "On line-perfect graphs",
8:
208:
152:
150:
146:
7:
14:
112:have the same size, and that the
16:Graph whose line graph is perfect
196:Journal of Combinatorial Theory
1:
210:10.1016/0095-8956(92)90028-V
376:
255:10.1007/978-3-642-78240-4
132:, a graph in which every
99:perfectly orderable graph
319:Mathematical Programming
295:10.1007/3-540-45477-2_29
160:Mathematical Programming
56:biconnected components
24:
22:
241:Schrijver, Alexander
110:minimum vertex cover
332:10.1007/BF01609025
173:10.1007/BF01593791
130:Strangulated graph
33:line perfect graph
25:
264:978-3-642-78242-8
233:Grötschel, Martin
367:
344:
342:
313:
307:
305:
282:
276:
275:
229:
223:
221:
212:
190:
184:
183:
154:
134:peripheral cycle
106:maximum matching
88:
73:
375:
374:
370:
369:
368:
366:
365:
364:
350:
349:
348:
347:
315:
314:
310:
284:
283:
279:
265:
231:
230:
226:
192:
191:
187:
156:
155:
148:
143:
126:
114:chromatic index
87:
78:
76:triangular book
72:
66:
60:bipartite graph
51:is a triangle.
17:
12:
11:
5:
373:
371:
363:
362:
360:Perfect graphs
352:
351:
346:
345:
326:(2): 236–238,
308:
277:
263:
237:Lovász, László
224:
185:
167:(2): 255–259,
145:
144:
142:
139:
138:
137:
125:
122:
118:maximum degree
82:
70:
64:complete graph
15:
13:
10:
9:
6:
4:
3:
2:
372:
361:
358:
357:
355:
341:
337:
333:
329:
325:
321:
320:
312:
309:
304:
300:
296:
292:
288:
281:
278:
274:
270:
266:
260:
256:
252:
248:
247:
242:
238:
234:
228:
225:
220:
216:
211:
206:
202:
198:
197:
189:
186:
182:
178:
174:
170:
166:
162:
161:
153:
151:
147:
140:
136:is a triangle
135:
131:
128:
127:
123:
121:
119:
115:
111:
107:
102:
100:
96:
95:Meyniel graph
92:
86:
81:
77:
69:
65:
61:
57:
52:
50:
46:
45:perfect graph
42:
38:
34:
30:
21:
323:
317:
311:
286:
280:
245:
227:
200:
199:, Series B,
194:
188:
164:
158:
103:
91:parity graph
84:
79:
67:
53:
49:simple cycle
32:
29:graph theory
26:
116:equals the
203:(1): 1–8,
141:References
41:line graph
354:Category
243:(1993),
124:See also
97:, and a
340:0509968
303:1905643
273:1261419
219:1159851
181:0457293
74:, or a
338:
301:
271:
261:
217:
179:
62:, the
39:whose
58:is a
43:is a
37:graph
35:is a
259:ISBN
108:and
93:, a
83:1,1,
31:, a
328:doi
291:doi
251:doi
205:doi
169:doi
27:In
356::
336:MR
334:,
324:15
322:,
299:MR
297:,
269:MR
267:,
257:,
239:;
235:;
215:MR
213:,
201:55
177:MR
175:,
165:12
163:,
149:^
120:.
101:.
343:.
330::
306:.
293::
253::
222:.
207::
171::
85:n
80:K
71:4
68:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
