79:, applied to the square of the line graph, shows that the strong chromatic index is at most quadratic in the maximum degree of the given graph, but better constant factors in the quadratic bound can be obtained by other methods.
94:
of every vertex is an induced matching. Neither of these types of graph can have a quadratic number of edges, but constructions are known for graphs of this type with nearly-quadratic numbers of edges.
178:
564:
Cameron, Kathie (2008), "Maximum
Induced Matchings for Chordal Graphs in Linear Time", Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987,
630:
Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (2012), "Graph products revisited: tight approximation hardness of induced matching, poset dimension and more",
348:
312:
86:
concerns the edge density of balanced bipartite graphs with linear strong chromatic index. Equivalently, it concerns the density of a different class of graphs, the
276:
252:
232:
208:
121:
696:
Graph-Theoretic
Concepts in Computer Science: 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22–24, 2016, Revised Selected Papers
711:
781:
457:
83:
385:
44:
776:
654:
604:
91:
452:
255:
36:) and these are the only edges connecting any two vertices which are endpoints of the matching edges (it is an
187:
690:
Xiao, Mingyu; Kou, Shaowei (2016), "Almost induced matching: linear kernels and parameterized algorithms", in
33:
546:, Colloq. Math. Soc. János Bolyai, vol. 18, Amsterdam and New York: North-Holland, pp. 939–945,
63:
The minimum number of induced matchings into which the edges of a graph can be partitioned is called its
150:
652:
Moser, Hannes; Sikdar, Somnath (2009), "The parameterized complexity of the induced matching problem",
144:
87:
71:
of the graph, the minimum number of matchings into which its edges can be partitioned. It equals the
317:
281:
180:
421:
Fouquet, J.-L.; Jolivet, J.-L. (1983), "Strong edge-colorings of graphs and applications to multi-
211:
539:
76:
707:
743:
699:
663:
613:
575:
510:
474:
466:
394:
351:
72:
37:
29:
757:
721:
677:
639:
589:
551:
522:
488:
438:
408:
753:
717:
691:
673:
635:
585:
547:
518:
484:
434:
404:
68:
698:, Lecture Notes in Computer Science, vol. 9941, Berlin: Springer, pp. 220–232,
261:
237:
217:
193:
106:
770:
580:
535:
140:
136:
132:
566:
363:
17:
734:
Xiao, Mingyu; Tan, Huan (2017), "Exact algorithms for maximum induced matching",
703:
632:
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on
Discrete Algorithms
124:
48:
399:
668:
617:
514:
52:
748:
470:
147:
occurs, the largest induced matching cannot be approximated to within any
544:
Combinatorics (Proc. Fifth
Hungarian Colloq., Keszthely, 1976), Vol. II
128:
542:(1978), "Triple systems with no six points carrying three triangles",
479:
190:, meaning that even finding a small induced matching of a given size
383:
Cameron, Kathie (2004), "Induced matchings in intersection graphs",
602:
Brandstaedt, Andreas; Hoang, Chinh (1989), "Induced matchings",
210:
is unlikely to have an algorithm significantly faster than the
455:(1997), "A bound on the strong chromatic index of a graph",
135:, because the squares of line graphs of chordal graphs are
127:(and thus, finding an induced matching of maximum size is
634:, Philadelphia, Pennsylvania: SIAM, pp. 1557–1576,
320:
284:
264:
254:
vertices whose removal leaves an induced matching is
240:
220:
196:
153:
109:
501:FronÄŤek, Dalibor (1989), "Locally linear graphs",
342:
306:
270:
246:
234:-tuples of edges. However, the problem of finding
226:
202:
172:
115:
43:An induced matching can also be described as an
139:. Moreover, it can be solved in linear time in
103:Finding an induced matching of size at least
8:
258:. The problem can also be solved exactly on
131:). It can be solved in polynomial time in
747:
667:
579:
478:
398:
331:
319:
295:
283:
263:
239:
219:
195:
158:
152:
108:
32:that do not share any vertices (it is a
375:
143:. Unless an unexpected collapse in the
7:
314:with exponential space, or in time
173:{\displaystyle n^{1-\varepsilon }}
75:of the square of the line graph.
14:
59:Strong coloring and neighborhoods
458:Journal of Combinatorial Theory
28:is a subset of the edges of an
337:
324:
301:
288:
1:
343:{\displaystyle O(1.4231^{n})}
307:{\displaystyle O(1.3752^{n})}
704:10.1007/978-3-662-53536-3_19
655:Discrete Applied Mathematics
605:Discrete Applied Mathematics
581:10.1016/0166-218X(92)90275-F
736:Information and Computation
798:
400:10.1016/j.disc.2003.05.001
669:10.1016/j.dam.2008.07.011
618:10.1007/s00453-007-9045-2
256:fixed-parameter tractable
749:10.1016/j.ic.2017.07.006
99:Computational complexity
782:Matching (graph theory)
278:-vertex graphs in time
214:approach of trying all
84:Ruzsa–Szemerédi problem
471:10.1006/jctb.1997.1724
344:
308:
272:
248:
228:
204:
174:
117:
67:, by analogy with the
65:strong chromatic index
345:
309:
273:
249:
229:
205:
175:
118:
88:locally linear graphs
777:Graph theory objects
386:Discrete Mathematics
318:
282:
262:
238:
218:
194:
186:The problem is also
183:in polynomial time.
151:
145:polynomial hierarchy
107:
55:of the given graph.
503:Mathematica Slovaca
181:approximation ratio
515:10338.dmlcz/136481
340:
304:
268:
244:
224:
212:brute force search
200:
170:
113:
713:978-3-662-53535-6
451:Molloy, Michael;
271:{\displaystyle n}
247:{\displaystyle k}
227:{\displaystyle k}
203:{\displaystyle k}
116:{\displaystyle k}
789:
761:
760:
751:
731:
725:
724:
692:Heggernes, Pinar
687:
681:
680:
671:
649:
643:
642:
627:
621:
620:
599:
593:
592:
583:
561:
555:
554:
532:
526:
525:
498:
492:
491:
482:
448:
442:
441:
427:Ars Combinatoria
424:
418:
412:
411:
402:
380:
352:polynomial space
349:
347:
346:
341:
336:
335:
313:
311:
310:
305:
300:
299:
277:
275:
274:
269:
253:
251:
250:
245:
233:
231:
230:
225:
209:
207:
206:
201:
179:
177:
176:
171:
169:
168:
122:
120:
119:
114:
73:chromatic number
38:induced subgraph
30:undirected graph
22:induced matching
797:
796:
792:
791:
790:
788:
787:
786:
767:
766:
765:
764:
733:
732:
728:
714:
689:
688:
684:
651:
650:
646:
629:
628:
624:
612:(1–3): 97–102,
601:
600:
596:
563:
562:
558:
534:
533:
529:
500:
499:
495:
450:
449:
445:
422:
420:
419:
415:
382:
381:
377:
372:
360:
327:
316:
315:
291:
280:
279:
260:
259:
236:
235:
216:
215:
192:
191:
154:
149:
148:
105:
104:
101:
77:Brooks' theorem
69:chromatic index
61:
45:independent set
26:strong matching
12:
11:
5:
795:
793:
785:
784:
779:
769:
768:
763:
762:
726:
712:
682:
662:(4): 715–727,
644:
622:
594:
556:
527:
493:
465:(2): 103–109,
443:
433:(A): 141–150,
413:
374:
373:
371:
368:
367:
366:
359:
356:
339:
334:
330:
326:
323:
303:
298:
294:
290:
287:
267:
243:
223:
199:
167:
164:
161:
157:
141:chordal graphs
137:perfect graphs
133:chordal graphs
112:
100:
97:
60:
57:
13:
10:
9:
6:
4:
3:
2:
794:
783:
780:
778:
775:
774:
772:
759:
755:
750:
745:
741:
737:
730:
727:
723:
719:
715:
709:
705:
701:
697:
693:
686:
683:
679:
675:
670:
665:
661:
657:
656:
648:
645:
641:
637:
633:
626:
623:
619:
615:
611:
607:
606:
598:
595:
591:
587:
582:
577:
573:
569:
568:
560:
557:
553:
549:
545:
541:
540:Szemerédi, E.
537:
531:
528:
524:
520:
516:
512:
508:
504:
497:
494:
490:
486:
481:
476:
472:
468:
464:
460:
459:
454:
447:
444:
440:
436:
432:
428:
417:
414:
410:
406:
401:
396:
392:
388:
387:
379:
376:
369:
365:
362:
361:
357:
355:
353:
332:
328:
321:
296:
292:
285:
265:
257:
241:
221:
213:
197:
189:
184:
182:
165:
162:
159:
155:
146:
142:
138:
134:
130:
126:
110:
98:
96:
93:
90:in which the
89:
85:
80:
78:
74:
70:
66:
58:
56:
54:
50:
46:
41:
39:
35:
31:
27:
23:
19:
739:
735:
729:
695:
685:
659:
653:
647:
631:
625:
609:
603:
597:
571:
567:Algorithmica
565:
559:
543:
536:Ruzsa, I. Z.
530:
506:
502:
496:
462:
461:, Series B,
456:
446:
430:
426:
416:
393:(1–3): 1–9,
390:
384:
378:
364:Induced path
185:
102:
92:neighborhood
81:
64:
62:
42:
25:
21:
18:graph theory
15:
742:: 196–211,
574:: 440–447,
453:Reed, Bruce
125:NP-complete
771:Categories
509:(1): 3–6,
370:References
53:line graph
480:1807/9474
166:ε
163:−
425:-gons",
358:See also
34:matching
758:3705425
722:3593958
694:(ed.),
678:2499485
640:3202998
590:1011265
552:0519318
523:1016323
489:1438613
439:0737086
409:2035386
129:NP-hard
51:of the
47:in the
756:
720:
710:
676:
638:
588:
550:
521:
487:
437:
407:
329:1.4231
293:1.3752
188:W-hard
49:square
350:with
20:, an
708:ISBN
82:The
744:doi
740:256
700:doi
664:doi
660:157
614:doi
576:doi
511:hdl
475:hdl
467:doi
395:doi
391:278
123:is
40:).
24:or
16:In
773::
754:MR
752:,
738:,
718:MR
716:,
706:,
674:MR
672:,
658:,
636:MR
610:24
608:,
586:MR
584:,
572:52
570:,
548:MR
538:;
519:MR
517:,
507:39
505:,
485:MR
483:,
473:,
463:69
435:MR
431:16
429:,
405:MR
403:,
389:,
354:.
746::
702::
666::
616::
578::
513::
477::
469::
423:k
397::
338:)
333:n
325:(
322:O
302:)
297:n
289:(
286:O
266:n
242:k
222:k
198:k
160:1
156:n
111:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.