844:
of a graph is another graph formed from it by contracting edges and by deleting edges and vertices. The Colin de Verdière invariant is minor-monotone, meaning that taking a minor of a graph can only decrease or leave unchanged its invariant:
1151:
The Colin de Verdière invariant is defined through a class of matrices corresponding to the graph instead of just a single matrix. Along the same lines other graph parameters can be defined and studied, such as the
562:
260:
899:
158:
470:
695:
393:
355:
630:
432:
1457:
1141:
316:
187:
114:
49:
1108:
591:
1077:
656:
290:
1051:
493:
1012:
781:
These same families of graphs also show up in connections between the Colin de Verdière invariant of a graph and the structure of its
1492:
1335:
1296:
1480:
1362:
1031:
996:
906:
1157:
1488:
1484:
1414:
1388:
1366:
1004:
1000:
52:
501:
199:
1553:
1237:
does not state this case explicitly, but it follows from his characterization of these graphs as the graphs with no
1161:
1548:
1358:
1330:
59:
1455:(1998), "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs",
1153:
67:
706:
Several well-known families of graphs can be characterized in terms of their Colin de Verdière invariants:
1448:
1410:
1393:, Bolyai Soc. Math. Stud., vol. 7, Budapest: János Bolyai Math. Soc., pp. 29–85, archived from
1380:
860:
972:
with at most μ + 1 colors. For instance, the linear forests have invariant 1, and can be
119:
1080:
991:
For graphs with Colin de Verdière invariant at most four, the conjecture remains true; these are the
841:
437:
1452:
1384:
1242:
661:
360:
321:
992:
985:
946:
770:
596:
398:
977:
742:
1143:
can both be drawn with a single crossing, and have Colin de Verdière invariant at most four.
1113:
949:
as the graphs with μ ≤ 4 and as the graphs with no
Petersen family minor. For
295:
163:
81:
25:
1513:
1466:
1426:
1344:
1306:
782:
194:
1371:
Graph
Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
1086:
995:, and the fact that they have chromatic number at most five is a consequence of a proof by
1373:, Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 137–147
973:
942:
930:
567:
1056:
635:
269:
1353:
1238:
1036:
969:
954:
478:
1521:
1542:
1504:
1348:
728:
981:
756:
1471:
62:
in 1990. It was motivated by the study of the maximum multiplicity of the second
1311:
1288:
941: = 4 the set of forbidden minors consists of the seven graphs in the
63:
1434:
1394:
1333:(1990), "Sur un nouvel invariant des graphes et un critère de planarité",
968:
conjectured that any graph with Colin de Verdière invariant μ may be
953: = 5 the set of forbidden minors includes the 78 graphs of the
1517:
1430:
1361:(1993), "On a new graph invariant and a criterion for planarity", in
190:
1415:"The Colin de Verdiere number and sphere representations of a graph"
1199:
1390:
921:
are the same as the graphs that do not have any member of
495:
has exactly one negative eigenvalue, of multiplicity 1;
1008:
917:
of graphs such that the graphs with invariant at most
1116:
1089:
1059:
1039:
863:
664:
638:
599:
570:
504:
481:
440:
401:
363:
324:
298:
272:
202:
166:
122:
84:
28:
957:, and it is conjectured that this list is complete.
1274:
1135:
1102:
1071:
1045:
893:
689:
650:
624:
585:
556:
487:
464:
426:
387:
349:
310:
284:
254:
181:
152:
108:
43:
1387:(1999), "The Colin de Verdière graph parameter",
1234:
1222:
965:
926:
557:{\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)}}
255:{\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)}}
1458:Proceedings of the American Mathematical Society
1257:
980:have invariant two, and can be 3-colored; the
1053:, it has Colin de Verdière invariant at most
8:
1289:"Graphs and obstructions in four dimensions"
1200:van der Holst, Lovász & Schrijver (1999)
453:
441:
376:
364:
147:
129:
945:, due to the two characterizations of the
1470:
1336:Journal of Combinatorial Theory, Series B
1310:
1121:
1115:
1094:
1088:
1058:
1038:
862:
669:
663:
637:
604:
598:
569:
542:
538:
537:
518:
503:
480:
439:
406:
400:
362:
329:
323:
297:
271:
240:
236:
235:
216:
201:
165:
121:
83:
27:
702:Characterization of known graph families
1270:
1268:
1266:
1218:
1216:
1214:
1212:
1210:
1208:
1195:
1193:
1191:
1189:
1187:
1185:
1183:
1181:
1179:
1177:
1173:
793:-vertex graph is a linear forest, then
1253:
1251:
7:
1275:Kotlov, Lovász & Vempala (1997)
894:{\displaystyle \mu (H)\leq \mu (G)}
808:-vertex graph is outerplanar, then
116:be a simple graph with vertex set
14:
498:(M3) there is no nonzero matrix
153:{\displaystyle V=\{1,\dots ,n\}}
1297:Journal of Combinatorial Theory
465:{\displaystyle \{i,j\}\notin E}
984:have invariant 3, and (by the
888:
882:
873:
867:
823:-vertex graph is planar, then
549:
543:
530:
511:
247:
241:
228:
209:
176:
170:
103:
91:
38:
32:
1:
1472:10.1090/S0002-9939-98-04244-0
1258:Lovász & Schrijver (1998)
690:{\displaystyle M_{i,j}\neq 0}
20:Colin de Verdière's invariant
1493:"Hadwiger's conjecture for K
1349:10.1016/0095-8956(90)90093-F
993:linklessly embeddable graphs
947:linklessly embeddable graphs
731:(a disjoint union of paths);
388:{\displaystyle \{i,j\}\in E}
350:{\displaystyle M_{i,j}<0}
1413:; Vempala, Santosh (1997),
1287:Hein van der Holst (2006).
1570:
1312:10.1016/j.jctb.2005.09.004
913:there exists a finite set
1158:minimum semidefinite rank
907:Robertson–Seymour theorem
625:{\displaystyle X_{i,j}=0}
427:{\displaystyle M_{i,j}=0}
1235:Colin de Verdière (1990)
1223:Colin de Verdière (1990)
1079:. For instance, the two
966:Colin de Verdière (1990)
927:Colin de Verdière (1990)
819:If the complement of an
804:If the complement of an
789:If the complement of an
1359:Colin de Verdière, Yves
1331:Colin de Verdière, Yves
1136:{\displaystyle K_{3,3}}
311:{\displaystyle i\neq j}
182:{\displaystyle \mu (G)}
109:{\displaystyle G=(V,E)}
44:{\displaystyle \mu (G)}
1137:
1104:
1073:
1047:
895:
691:
652:
626:
587:
558:
489:
466:
428:
389:
351:
312:
286:
256:
183:
154:
110:
60:Yves Colin de Verdière
45:
1379:van der Holst, Hein;
1138:
1105:
1103:{\displaystyle K_{5}}
1074:
1048:
896:
771:linklessly embeddable
692:
653:
627:
588:
559:
490:
467:
429:
390:
352:
313:
287:
257:
184:
155:
111:
68:Schrödinger operators
46:
22:is a graph parameter
1453:Schrijver, Alexander
1385:Schrijver, Alexander
1114:
1087:
1057:
1037:
1022:-minor-free graphs.
988:) can be 4-colored.
937: ≤ 3; for
929:lists these sets of
861:
717:has only one vertex;
662:
636:
597:
586:{\displaystyle MX=0}
568:
502:
479:
438:
399:
361:
322:
296:
270:
200:
164:
120:
82:
26:
1072:{\displaystyle k+3}
1013:Hadwiger conjecture
651:{\displaystyle i=j}
285:{\displaystyle i,j}
1554:Graph minor theory
1518:10.1007/BF01202354
1431:10.1007/BF01195002
1133:
1100:
1069:
1043:
997:Neil Robertson
986:four color theorem
978:outerplanar graphs
891:
687:
648:
622:
583:
554:
485:
462:
424:
385:
347:
308:
282:
252:
179:
150:
106:
41:
1162:minimum skew rank
1046:{\displaystyle k}
488:{\displaystyle M}
1561:
1549:Graph invariants
1534:
1533:
1532:
1526:
1520:, archived from
1501:
1475:
1474:
1465:(5): 1275–1285,
1444:
1443:
1442:
1433:, archived from
1409:Kotlov, Andrew;
1404:
1403:
1402:
1374:
1352:. Translated by
1351:
1317:
1316:
1314:
1293:
1284:
1278:
1272:
1261:
1255:
1246:
1232:
1226:
1220:
1203:
1197:
1142:
1140:
1139:
1134:
1132:
1131:
1109:
1107:
1106:
1101:
1099:
1098:
1078:
1076:
1075:
1070:
1052:
1050:
1049:
1044:
1026:Other properties
961:Chromatic number
931:forbidden minors
900:
898:
897:
892:
830:
815:
800:
764:
750:
736:
722:
712:
696:
694:
693:
688:
680:
679:
657:
655:
654:
649:
631:
629:
628:
623:
615:
614:
592:
590:
589:
584:
563:
561:
560:
555:
553:
552:
541:
529:
528:
494:
492:
491:
486:
471:
469:
468:
463:
433:
431:
430:
425:
417:
416:
394:
392:
391:
386:
356:
354:
353:
348:
340:
339:
317:
315:
314:
309:
291:
289:
288:
283:
261:
259:
258:
253:
251:
250:
239:
227:
226:
195:symmetric matrix
188:
186:
185:
180:
159:
157:
156:
151:
115:
113:
112:
107:
50:
48:
47:
42:
1569:
1568:
1564:
1563:
1562:
1560:
1559:
1558:
1539:
1538:
1530:
1528:
1524:
1499:
1496:
1481:Robertson, Neil
1479:
1447:
1440:
1438:
1408:
1400:
1398:
1378:
1363:Robertson, Neil
1357:
1329:
1326:
1321:
1320:
1291:
1286:
1285:
1281:
1273:
1264:
1256:
1249:
1233:
1229:
1221:
1206:
1198:
1175:
1170:
1149:
1117:
1112:
1111:
1090:
1085:
1084:
1055:
1054:
1035:
1034:
1032:crossing number
1030:If a graph has
1028:
1021:
963:
943:Petersen family
859:
858:
838:
824:
809:
794:
765:if and only if
762:
751:if and only if
748:
737:if and only if
734:
723:if and only if
720:
713:if and only if
710:
704:
665:
660:
659:
634:
633:
600:
595:
594:
566:
565:
536:
514:
500:
499:
477:
476:
436:
435:
402:
397:
396:
359:
358:
325:
320:
319:
294:
293:
268:
267:
234:
212:
198:
197:
189:is the largest
162:
161:
118:
117:
80:
79:
76:
24:
23:
17:
12:
11:
5:
1567:
1565:
1557:
1556:
1551:
1541:
1540:
1537:
1536:
1494:
1477:
1449:Lovász, László
1445:
1425:(4): 483–521,
1411:Lovász, László
1406:
1381:Lovász, László
1376:
1354:Neil J. Calkin
1325:
1322:
1319:
1318:
1305:(3): 388–404.
1279:
1262:
1247:
1227:
1204:
1172:
1171:
1169:
1166:
1148:
1145:
1130:
1127:
1124:
1120:
1097:
1093:
1068:
1065:
1062:
1042:
1027:
1024:
1019:
1003:, and
962:
959:
955:Heawood family
903:
902:
890:
887:
884:
881:
878:
875:
872:
869:
866:
853:is a minor of
837:
834:
833:
832:
817:
802:
779:
778:
760:
746:
732:
718:
703:
700:
699:
698:
686:
683:
678:
675:
672:
668:
647:
644:
641:
621:
618:
613:
610:
607:
603:
593:and such that
582:
579:
576:
573:
551:
548:
545:
540:
535:
532:
527:
524:
521:
517:
513:
510:
507:
496:
484:
473:
461:
458:
455:
452:
449:
446:
443:
423:
420:
415:
412:
409:
405:
384:
381:
378:
375:
372:
369:
366:
346:
343:
338:
335:
332:
328:
307:
304:
301:
281:
278:
275:
249:
246:
243:
238:
233:
230:
225:
222:
219:
215:
211:
208:
205:
178:
175:
172:
169:
149:
146:
143:
140:
137:
134:
131:
128:
125:
105:
102:
99:
96:
93:
90:
87:
75:
72:
58:introduced by
40:
37:
34:
31:
16:Graph property
15:
13:
10:
9:
6:
4:
3:
2:
1566:
1555:
1552:
1550:
1547:
1546:
1544:
1527:on 2009-04-10
1523:
1519:
1515:
1511:
1507:
1506:
1505:Combinatorica
1498:
1497:-free graphs"
1490:
1489:Thomas, Robin
1486:
1485:Seymour, Paul
1482:
1478:
1473:
1468:
1464:
1460:
1459:
1454:
1450:
1446:
1437:on 2016-03-03
1436:
1432:
1428:
1424:
1420:
1419:Combinatorica
1416:
1412:
1407:
1397:on 2016-03-03
1396:
1392:
1391:
1386:
1382:
1377:
1372:
1368:
1367:Seymour, Paul
1364:
1360:
1355:
1350:
1346:
1342:
1338:
1337:
1332:
1328:
1327:
1323:
1313:
1308:
1304:
1300:
1298:
1290:
1283:
1280:
1276:
1271:
1269:
1267:
1263:
1259:
1254:
1252:
1248:
1244:
1240:
1236:
1231:
1228:
1224:
1219:
1217:
1215:
1213:
1211:
1209:
1205:
1201:
1196:
1194:
1192:
1190:
1188:
1186:
1184:
1182:
1180:
1178:
1174:
1167:
1165:
1163:
1159:
1155:
1146:
1144:
1128:
1125:
1122:
1118:
1095:
1091:
1082:
1066:
1063:
1060:
1040:
1033:
1025:
1023:
1018:
1014:
1010:
1006:
1002:
998:
994:
989:
987:
983:
982:planar graphs
979:
975:
971:
967:
960:
958:
956:
952:
948:
944:
940:
936:
932:
928:
924:
920:
916:
912:
908:
885:
879:
876:
870:
864:
856:
852:
848:
847:
846:
843:
835:
828:
822:
818:
813:
807:
803:
798:
792:
788:
787:
786:
784:
776:
772:
768:
761:
758:
754:
747:
744:
740:
733:
730:
729:linear forest
726:
719:
716:
709:
708:
707:
701:
684:
681:
676:
673:
670:
666:
645:
642:
639:
619:
616:
611:
608:
605:
601:
580:
577:
574:
571:
546:
533:
525:
522:
519:
515:
508:
505:
497:
482:
474:
459:
456:
450:
447:
444:
421:
418:
413:
410:
407:
403:
382:
379:
373:
370:
367:
344:
341:
336:
333:
330:
326:
305:
302:
299:
279:
276:
273:
266:(M1) for all
265:
264:
263:
244:
231:
223:
220:
217:
213:
206:
203:
196:
192:
173:
167:
144:
141:
138:
135:
132:
126:
123:
100:
97:
94:
88:
85:
73:
71:
69:
65:
61:
57:
54:
35:
29:
21:
1529:, retrieved
1522:the original
1509:
1503:
1462:
1456:
1439:, retrieved
1435:the original
1422:
1418:
1399:, retrieved
1395:the original
1389:
1370:
1343:(1): 11–21,
1340:
1334:
1302:
1295:
1282:
1230:
1154:minimum rank
1150:
1029:
1016:
1005:Robin Thomas
1001:Paul Seymour
990:
964:
950:
938:
934:
925:as a minor.
922:
918:
914:
910:
909:, for every
904:
854:
850:
839:
836:Graph minors
826:
820:
811:
805:
796:
790:
780:
774:
766:
752:
738:
724:
714:
705:
77:
55:
19:
18:
1512:: 279–361,
743:outerplanar
262:such that:
66:of certain
1543:Categories
1531:2010-08-06
1441:2010-08-06
1401:2010-08-06
1324:References
1299:, Series B
1081:Kuratowski
783:complement
763:μ ≤ 4
749:μ ≤ 3
735:μ ≤ 2
721:μ ≤ 1
711:μ ≤ 0
632:if either
564:such that
74:Definition
64:eigenvalue
1147:Influence
1011:) of the
974:2-colored
880:μ
877:≤
865:μ
829:− 5
825:μ ≥
814:− 4
810:μ ≥
799:− 3
795:μ ≥
682:≠
534:∈
457:∉
380:∈
303:≠
232:∈
168:μ
139:…
30:μ
1491:(1993),
1369:(eds.),
1239:triangle
51:for any
1083:graphs
1007: (
970:colored
905:By the
193:of any
160:. Then
1245:minor.
999:,
976:; the
757:planar
395:, and
191:corank
1525:(PDF)
1500:(PDF)
1292:(PDF)
1168:Notes
857:then
842:minor
727:is a
697:hold.
475:(M2)
292:with
53:graph
1243:claw
1160:and
1110:and
1015:for
1009:1993
933:for
769:is
342:<
78:Let
1514:doi
1467:doi
1463:126
1427:doi
1356:as
1345:doi
1307:doi
1241:or
849:If
773:in
755:is
741:is
658:or
434:if
357:if
1545::
1510:13
1508:,
1502:,
1487:;
1483:;
1461:,
1451:;
1423:17
1421:,
1417:,
1383:;
1365:;
1341:50
1339:,
1303:96
1301:.
1294:.
1265:^
1250:^
1207:^
1176:^
1164:.
1156:,
840:A
785::
318::
70:.
56:G,
1535:.
1516::
1495:6
1476:.
1469::
1429::
1405:.
1375:.
1347::
1315:.
1309::
1277:.
1260:.
1225:.
1202:.
1129:3
1126:,
1123:3
1119:K
1096:5
1092:K
1067:3
1064:+
1061:k
1041:k
1020:6
1017:K
951:k
939:k
935:k
923:H
919:k
915:H
911:k
901:.
889:)
886:G
883:(
874:)
871:H
868:(
855:G
851:H
831:.
827:n
821:n
816:;
812:n
806:n
801:;
797:n
791:n
777:.
775:R
767:G
759:;
753:G
745:;
739:G
725:G
715:G
685:0
677:j
674:,
671:i
667:M
646:j
643:=
640:i
620:0
617:=
612:j
609:,
606:i
602:X
581:0
578:=
575:X
572:M
550:)
547:n
544:(
539:R
531:)
526:j
523:,
520:i
516:X
512:(
509:=
506:X
483:M
472:;
460:E
454:}
451:j
448:,
445:i
442:{
422:0
419:=
414:j
411:,
408:i
404:M
383:E
377:}
374:j
371:,
368:i
365:{
345:0
337:j
334:,
331:i
327:M
306:j
300:i
280:j
277:,
274:i
248:)
245:n
242:(
237:R
229:)
224:j
221:,
218:i
214:M
210:(
207:=
204:M
177:)
174:G
171:(
148:}
145:n
142:,
136:,
133:1
130:{
127:=
124:V
104:)
101:E
98:,
95:V
92:(
89:=
86:G
39:)
36:G
33:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.