20:
62:, the graph of moves of a chess king on a chessboard, which can be constructed as a strong product of path graphs. Decompositions of planar graphs and related graph classes into strong products have been used as a central tool to prove many other results about these graphs.
42:
is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different
263:. Its horizontal edges come from the Cartesian product, and its diagonal edges come from the tensor product of the same two paths. Together, these two kinds of edges make up the entire strong product.
1113:
566:
518:
47:
operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the
652:, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341,
467:
447:
427:
407:
387:
367:
347:
848:
Gawrychowski, Pawel; Janczewski, Wojciech (2022), "Simpler adjacency labeling for planar graphs with B-trees", in
Bringmann, Karl; Chan, Timothy (eds.),
1178:
625:
741:
911:
318:
of the strong product of any two graphs equals the product of the clique numbers of the two graphs. If two graphs both have bounded
329:
is a graph formed from the leaves of a tree by making two leaves adjacent when their distance in the tree is below some threshold
300:
569:
1303:
Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: small classes",
1267:
91:
241:
48:
1238:
1173:
1108:
946:
915:
736:
686:
572:, implying that their chromatic number is at least 10. However, it is not known whether these graphs are biplanar.
291:, and bounded nonrepetitive chromatic number and centered chromatic number. This product structure can be found in
971:
Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved bounds for centered colorings",
245:
52:
1455:
525:
531:
483:
590:
322:, and in addition one of them has bounded degree, then their strong product also has bounded twin-width.
1265:
Kozawa, Kyohei; Otachi, Yota; Yamazaki, Koichi (2014), "Lower bounds for treewidth of product graphs",
568:. In both cases, the number of vertices in these graphs is more than 9 times the size of their largest
850:
5th
Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022
1391:
1365:
1312:
1246:
1213:
1187:
1148:
1122:
1088:
1059:
1033:
1002:
976:
923:
887:
861:
813:
804:
778:
750:
700:
691:
237:
621:
1424:
1416:
1375:
1322:
1276:
1230:
1197:
1165:
1132:
1043:
986:
942:
853:
823:
795:
760:
710:
678:
598:
1436:
1387:
1334:
1290:
1209:
1144:
1055:
998:
958:
835:
774:
722:
657:
642:
295:. Beyond planar graphs, extensions of these results have been proven for graphs of bounded
1432:
1383:
1330:
1286:
1205:
1140:
1051:
994:
954:
831:
770:
718:
653:
296:
284:
252:
59:
24:
1351:
1347:
521:
477:
469:-vertex cycle. This embedding has been used in recognition algorithms for leaf powers.
452:
432:
412:
392:
372:
352:
332:
308:
288:
164:
69:
in the literature, since it has also been used to denote the tensor product of graphs.
1449:
1423:, Problem Books in Mathematics, Springer International Publishing, pp. 115–133,
1408:
1395:
1217:
1152:
1063:
1006:
865:
782:
315:
259:
and whose edges represent possible moves of a chess king, is a strong product of two
44:
1412:
1356:
1024:
280:
272:
35:
1428:
907:
473:
292:
279:
at most six. This result has been used to prove that planar graphs have bounded
1379:
1047:
1281:
1201:
857:
528:; another suggested example is the graph obtained by removing any vertex from
326:
319:
304:
260:
256:
28:
602:
1234:
1169:
1080:
1019:
879:
799:
682:
276:
19:
739:; Yi, Wendy (2022), "An improved planar graph product structure theorem",
1076:
1352:"Parameterized leaf power recognition via embedding into graph products"
1136:
1022:(2021), "A fast algorithm for the product structure of planar graphs",
990:
1326:
949:(2020), "Planar graphs have bounded nonrepetitive chromatic number",
827:
714:
1370:
1317:
1251:
1192:
1127:
1093:
1038:
981:
928:
892:
818:
765:
755:
705:
852:, Society for Industrial and Applied Mathematics, pp. 24–36,
18:
798:; Esperet, Louis; Gavoille, Cyril; Joret, Gwenaël; Micek, Piotr;
1085:
An optimal algorithm for the product structure of planar graphs
802:(2021), "Adjacency labelling for planar graphs (and beyond)",
1111:(2022), "Improved product structure for graphs on surfaces",
616:
Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008),
275:
is a subgraph of a strong product of a path and a graph of
1176:(2022), "Clustered 3-colouring graphs of bounded degree",
520:, has been suggested as a possibility for a 10-chromatic
1421:
Graph Theory: Favorite
Conjectures and Open Problems, II
1114:
650:
2005 International
Conference on Analysis of Algorithms
641:
Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005),
307:, bounded-degree graphs with any forbidden minor, and
534:
486:
455:
435:
415:
395:
375:
355:
335:
1243:
Graph product structure for non-minor-closed classes
945:; Esperet, Louis; Joret, Gwenaël; Walczak, Bartosz;
65:
Care should be exercised when encountering the term
689:(2020), "Planar graphs have bounded queue-number",
1107:Distel, Marc; Hickingbotham, Robert; Huynh, Tony;
560:
512:
461:
441:
429:can be found as a subgraph of a strong product of
421:
401:
381:
361:
341:
643:"Two-anticoloring of planar and related graphs"
593:(1979), "On the Shannon Capacity of a Graph",
8:
524:that would improve the known bounds on the
920:Universality in minor-closed graph classes
255:, a graph whose vertices are squares of a
1369:
1316:
1280:
1250:
1191:
1126:
1092:
1037:
980:
927:
891:
817:
764:
754:
704:
552:
539:
533:
504:
491:
485:
454:
434:
414:
394:
374:
354:
334:
1179:Combinatorics, Probability and Computing
673:
671:
669:
667:
595:IEEE Transactions on Information Theory
581:
101:is a graph such that the vertex set of
58:An example of a strong product is the
1411:(2018), "To the Moon and beyond", in
884:Sparse universal graphs for planarity
7:
561:{\displaystyle C_{5}\boxtimes K_{4}}
513:{\displaystyle C_{7}\boxtimes K_{4}}
742:Electronic Journal of Combinatorics
618:Graphs and their Cartesian Product
14:
1419:; Hedetniemi, Stephen T. (eds.),
472:The strong product of a 7-vertex
878:Esperet, Louis; Joret, Gwenaël;
681:; Joret, Gwenaël; Micek, Piotr;
16:Binary operation in graph theory
1:
1429:10.1007/978-3-319-97686-0_11
1268:Discrete Applied Mathematics
267:Properties and applications
49:Cartesian product of graphs
1472:
1380:10.1007/s00453-020-00720-8
1048:10.1007/s00453-020-00793-5
289:adjacency labeling schemes
27:, a strong product of two
1350:; Havvaei, Elham (2020),
1282:10.1016/j.dam.2013.08.005
1202:10.1017/s0963548321000213
973:Advances in Combinatorics
951:Advances in Combinatorics
858:10.1137/1.9781611977066.3
111:is the Cartesian product
603:10.1109/TIT.1979.1055985
130:; and distinct vertices
53:tensor product of graphs
1083:; Odak, Saeed (2022),
562:
514:
463:
443:
423:
403:
389:-leaf power of a tree
383:
363:
343:
73:Definition and example
31:
749:(2), Paper No. 2.51,
685:; Ueckerdt, Torsten;
563:
515:
464:
444:
424:
404:
384:
364:
344:
22:
1305:Combinatorial Theory
1172:; Walczak, Bartosz;
532:
484:
453:
433:
413:
393:
373:
353:
333:
1311:(2): P10:1–P10:42,
1137:10.46298/dmtcs.8877
953:: Paper No. 5, 11,
735:Ueckerdt, Torsten;
1168:; Esperet, Louis;
1121:(2): Paper No. 6,
991:10.19086/aic.27351
912:Thomassen, Carsten
812:(6): Art. 42, 33,
805:Journal of the ACM
699:(4): Art. 22, 38,
692:Journal of the ACM
597:, IT-25 (1): 1–7,
558:
526:Earth–Moon problem
510:
459:
439:
419:
399:
379:
359:
339:
32:
1417:Haynes, Teresa W.
1327:10.5070/C62257876
910:; Šámal, Robert;
627:978-1-56881-429-2
462:{\displaystyle k}
442:{\displaystyle G}
422:{\displaystyle T}
402:{\displaystyle T}
382:{\displaystyle k}
362:{\displaystyle G}
342:{\displaystyle k}
251:For example, the
242:Cartesian product
1463:
1440:
1439:
1405:
1399:
1398:
1373:
1364:(8): 2337–2359,
1344:
1338:
1337:
1320:
1300:
1294:
1293:
1284:
1262:
1256:
1255:
1254:
1227:
1221:
1220:
1195:
1162:
1156:
1155:
1130:
1104:
1098:
1097:
1096:
1073:
1067:
1066:
1041:
1032:(5): 1544–1558,
1016:
1010:
1009:
984:
968:
962:
961:
939:
933:
932:
931:
903:
897:
896:
895:
875:
869:
868:
845:
839:
838:
821:
792:
786:
785:
768:
758:
732:
726:
725:
708:
675:
662:
660:
647:
638:
632:
630:
620:, A. K. Peters,
613:
607:
605:
586:
567:
565:
564:
559:
557:
556:
544:
543:
519:
517:
516:
511:
509:
508:
496:
495:
468:
466:
465:
460:
448:
446:
445:
440:
428:
426:
425:
420:
408:
406:
405:
400:
388:
386:
385:
380:
368:
366:
365:
360:
348:
346:
345:
340:
299:, graphs with a
285:universal graphs
231:
227:
223:
219:
210:
206:
202:
187:
183:
179:
163:
154:are adjacent in
153:
141:
129:
110:
100:
96:
89:
1471:
1470:
1466:
1465:
1464:
1462:
1461:
1460:
1446:
1445:
1444:
1443:
1407:
1406:
1402:
1348:Eppstein, David
1346:
1345:
1341:
1302:
1301:
1297:
1264:
1263:
1259:
1229:
1228:
1224:
1164:
1163:
1159:
1106:
1105:
1101:
1077:Bose, Prosenjit
1075:
1074:
1070:
1018:
1017:
1013:
975:, Paper No. 8,
970:
969:
965:
941:
940:
936:
905:
904:
900:
877:
876:
872:
847:
846:
842:
828:10.1145/3477542
794:
793:
789:
734:
733:
729:
715:10.1145/3385731
677:
676:
665:
645:
640:
639:
635:
628:
615:
614:
610:
589:
587:
583:
578:
570:independent set
548:
535:
530:
529:
500:
487:
482:
481:
476:and a 4-vertex
451:
450:
431:
430:
411:
410:
391:
390:
371:
370:
351:
350:
331:
330:
309:k-planar graphs
301:forbidden minor
269:
229:
228:is adjacent to
225:
221:
220:is adjacent to
217:
208:
207:is adjacent to
204:
194:
185:
184:is adjacent to
181:
171:
155:
143:
131:
112:
102:
98:
94:
81:
75:
17:
12:
11:
5:
1469:
1467:
1459:
1458:
1456:Graph products
1448:
1447:
1442:
1441:
1409:Gethner, Ellen
1400:
1339:
1295:
1257:
1239:Wood, David R.
1231:Dujmović, Vida
1222:
1186:(1): 123–135,
1174:Wood, David R.
1166:Dujmović, Vida
1157:
1109:Wood, David R.
1099:
1068:
1011:
963:
947:Wood, David R.
943:Dujmović, Vida
934:
916:Wood, David R.
898:
870:
840:
796:Dujmović, Vida
787:
766:10.37236/10614
737:Wood, David R.
727:
687:Wood, David R.
679:Dujmović, Vida
663:
633:
626:
608:
591:Lovász, László
588:See page 2 of
580:
579:
577:
574:
555:
551:
547:
542:
538:
522:biplanar graph
507:
503:
499:
494:
490:
478:complete graph
458:
438:
418:
398:
378:
358:
338:
268:
265:
246:tensor product
234:
233:
215:
192:
165:if and only if
79:strong product
74:
71:
67:strong product
40:strong product
15:
13:
10:
9:
6:
4:
3:
2:
1468:
1457:
1454:
1453:
1451:
1438:
1434:
1430:
1426:
1422:
1418:
1414:
1413:Gera, Ralucca
1410:
1404:
1401:
1397:
1393:
1389:
1385:
1381:
1377:
1372:
1367:
1363:
1359:
1358:
1353:
1349:
1343:
1340:
1336:
1332:
1328:
1324:
1319:
1314:
1310:
1306:
1299:
1296:
1292:
1288:
1283:
1278:
1274:
1270:
1269:
1261:
1258:
1253:
1248:
1244:
1240:
1236:
1232:
1226:
1223:
1219:
1215:
1211:
1207:
1203:
1199:
1194:
1189:
1185:
1181:
1180:
1175:
1171:
1167:
1161:
1158:
1154:
1150:
1146:
1142:
1138:
1134:
1129:
1124:
1120:
1116:
1115:
1110:
1103:
1100:
1095:
1090:
1086:
1082:
1078:
1072:
1069:
1065:
1061:
1057:
1053:
1049:
1045:
1040:
1035:
1031:
1027:
1026:
1021:
1015:
1012:
1008:
1004:
1000:
996:
992:
988:
983:
978:
974:
967:
964:
960:
956:
952:
948:
944:
938:
935:
930:
925:
921:
917:
913:
909:
906:Huynh, Tony;
902:
899:
894:
889:
885:
881:
874:
871:
867:
863:
859:
855:
851:
844:
841:
837:
833:
829:
825:
820:
815:
811:
807:
806:
801:
797:
791:
788:
784:
780:
776:
772:
767:
762:
757:
752:
748:
744:
743:
738:
731:
728:
724:
720:
716:
712:
707:
702:
698:
694:
693:
688:
684:
680:
674:
672:
670:
668:
664:
659:
655:
651:
644:
637:
634:
629:
623:
619:
612:
609:
604:
600:
596:
592:
585:
582:
575:
573:
571:
553:
549:
545:
540:
536:
527:
523:
505:
501:
497:
492:
488:
479:
475:
470:
456:
436:
416:
396:
376:
356:
336:
328:
323:
321:
317:
316:clique number
312:
310:
306:
302:
298:
294:
290:
286:
282:
278:
274:
266:
264:
262:
258:
254:
249:
247:
243:
239:
216:
214:
201:
197:
193:
191:
178:
174:
170:
169:
168:
166:
162:
158:
151:
147:
139:
135:
127:
123:
119:
115:
109:
105:
93:
88:
84:
80:
72:
70:
68:
63:
61:
56:
54:
50:
46:
45:graph product
41:
37:
30:
26:
21:
1420:
1403:
1361:
1357:Algorithmica
1355:
1342:
1308:
1304:
1298:
1272:
1266:
1260:
1242:
1225:
1183:
1177:
1160:
1118:
1112:
1102:
1084:
1071:
1029:
1025:Algorithmica
1023:
1014:
972:
966:
950:
937:
919:
908:Mohar, Bojan
901:
883:
873:
849:
843:
809:
803:
790:
746:
740:
730:
696:
690:
649:
636:
617:
611:
594:
584:
471:
324:
313:
287:and concise
281:queue number
273:planar graph
270:
253:king's graph
250:
235:
212:
199:
195:
189:
176:
172:
160:
156:
149:
145:
137:
133:
125:
121:
117:
113:
107:
103:
86:
82:
78:
76:
66:
64:
60:king's graph
57:
39:
36:graph theory
33:
25:king's graph
1275:: 251–258,
474:cycle graph
303:that is an
293:linear time
261:path graphs
29:path graphs
1371:1810.02452
1318:2006.09877
1252:1907.05168
1235:Morin, Pat
1193:2002.11721
1170:Morin, Pat
1128:2112.10025
1094:2202.08870
1081:Morin, Pat
1039:2004.02530
1020:Morin, Pat
982:1907.04586
929:2109.00327
893:2010.05779
880:Morin, Pat
819:2003.04280
800:Morin, Pat
756:2108.00198
706:1904.04791
683:Morin, Pat
576:References
327:leaf power
320:twin-width
305:apex graph
257:chessboard
236:It is the
1396:254032445
1218:211532824
1153:245335306
1064:254028754
1007:195874032
866:245738461
783:236772054
546:⊠
498:⊠
277:treewidth
1450:Category
1241:(2019),
918:(2021),
882:(2020),
283:, small
244:and the
51:and the
1437:3930641
1388:4132894
1335:4449818
1291:3128527
1210:4356460
1145:4504777
1056:4242109
999:4309118
959:4125346
836:4402353
775:4441087
723:4148600
658:2193130
449:with a
409:, then
240:of the
1435:
1394:
1386:
1333:
1289:
1216:
1208:
1151:
1143:
1062:
1054:
1005:
997:
957:
864:
834:
781:
773:
721:
656:
624:
271:Every
92:graphs
38:, the
1392:S2CID
1366:arXiv
1313:arXiv
1247:arXiv
1214:S2CID
1188:arXiv
1149:S2CID
1123:arXiv
1089:arXiv
1060:S2CID
1034:arXiv
1003:S2CID
977:arXiv
924:arXiv
888:arXiv
862:S2CID
814:arXiv
779:S2CID
751:arXiv
701:arXiv
646:(PDF)
369:is a
349:. If
297:genus
238:union
622:ISBN
314:The
224:and
203:and
180:and
142:and
120:) ×
97:and
77:The
23:The
1425:doi
1376:doi
1323:doi
1277:doi
1273:162
1198:doi
1133:doi
1044:doi
987:doi
854:doi
824:doi
761:doi
711:doi
599:doi
200:v'
196:u'
150:v'
138:u'
90:of
34:In
1452::
1433:MR
1431:,
1415:;
1390:,
1384:MR
1382:,
1374:,
1362:82
1360:,
1354:,
1331:MR
1329:,
1321:,
1307:,
1287:MR
1285:,
1271:,
1245:,
1237:;
1233:;
1212:,
1206:MR
1204:,
1196:,
1184:31
1182:,
1147:,
1141:MR
1139:,
1131:,
1119:24
1117:,
1087:,
1079:;
1058:,
1052:MR
1050:,
1042:,
1030:83
1028:,
1001:,
995:MR
993:,
985:,
955:MR
922:,
914:;
886:,
860:,
832:MR
830:,
822:,
810:68
808:,
777:,
771:MR
769:,
759:,
747:29
745:,
719:MR
717:,
709:,
697:67
695:,
666:^
654:MR
648:,
480:,
325:A
311:.
248:.
230:v'
226:u'
213:or
211:,
198:=
190:or
188:,
186:v'
182:u'
175:=
167::
159:⊠
106:⊠
85:⊠
55:.
1427::
1378::
1368::
1325::
1315::
1309:2
1279::
1249::
1200::
1190::
1135::
1125::
1091::
1046::
1036::
989::
979::
926::
890::
856::
826::
816::
763::
753::
713::
703::
661:.
631:.
606:.
601::
554:4
550:K
541:5
537:C
506:4
502:K
493:7
489:C
457:k
437:G
417:T
397:T
377:k
357:G
337:k
232:.
222:v
218:u
209:v
205:u
177:v
173:u
161:H
157:G
152:)
148:,
146:v
144:(
140:)
136:,
134:u
132:(
128:)
126:H
124:(
122:V
118:G
116:(
114:V
108:H
104:G
99:H
95:G
87:H
83:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
