Forbidden graph characterization: Difference between revisions
Line 165: | Line 165: | ||
| mr = 0505860 }}</ref> |
| mr = 0505860 }}</ref> |
||
|- |
|- |
||
| [[treewidth]] ≤ 2 ([[branchwidth]] ≤ 2) |
| series-parallel [[treewidth]] ≤ 2 ([[branchwidth]] ≤ 2) |
||
| ''K''<sub>4</sub> |
| ''K''<sub>4</sub> |
||
| graph minor |
| graph minor |
Revision as of 14:36, 19 November 2012
A forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures. Families vary in the nature of what is forbidden. In general, a structure G is a member of a family if and only if a forbidden substructure is not contained in G. The forbidden substructure might simply be a subgraph, or a substructure from which one might derive (via, e.g., edge contraction or subdivision) that which is forbidden. Thus, the forbidden structure might be one of:
- subgraphs,
- graph minors,
- homeomorphic subgraphs (also called topological minors).
(Such forbidden structures can also be called obstruction sets.)
Forbidden graph characterizations are utilized in combinatorial algorithms, often for identifying a structure. Such methods can provide a polynomial-time algorithm for determining a graph's membership in a specific family (i.e., a polynomial-time implementation of an indicator function).
A well-known characterization of this kind is the Kuratowski theorem that provides two forbidden homeomorphic subgraphs, using which, one may determine a graph's planarity. Another is the Robertson–Seymour theorem that proves the existence of a forbidden minor characterization for several graph families.
List of forbidden characterizations for graphs and hypergraphs
![]() |
Family | Forbidden graphs | Relation | Reference | |
---|---|---|---|---|
Forests | loops, pairs of parallel edges, and cycles of all lengths | subgraph | Definition | |
a loop (for multigraphs) or a triangle K3 (for simple graphs) | graph minor | Definition | ||
Claw-free graphs | star K1,3 | induced subgraph | Definition | |
Comparability graphs | induced subgraph | |||
Triangle-free graphs | triangle K3 | induced subgraph | Definition | |
Planar graphs | K5 and K3,3 | homeomorphic subgraph | Kuratowski theorem | |
K5 and K3,3 | graph minor | Wagner's theorem | ||
Outerplanar graphs | K4 and K2,3 | graph minor | Diestel (2000),[1] p. 107 | |
Graphs of fixed genus | a finite obstruction set | graph minor | Diestel (2000),[1] p. 275 | |
Apex graphs | a finite obstruction set | graph minor | [2] | |
Linklessly embeddable graphs | The Petersen family | graph minor | [3] | |
Bipartite graphs | odd cycles | subgraph | [4] | |
Chordal graphs | cycles of length 4 or more | induced subgraph | [5] | |
Perfect graphs | cycles of odd length 5 or more or their complements | induced subgraph | [6] | |
Line graph of graphs | nine forbidden subgraphs (listed here) | induced subgraph | [7] | |
Graph unions of cactus graphs | the four-vertex diamond graph formed by removing an edge from the complete graph K4 | graph minor | [8] | |
Ladder graphs | K2,3 and its dual graph | homeomorphic subgraph | [9] | |
Helly circular-arc graphs | induced subgraph | [10] | ||
split graphs | induced subgraph | [11] | ||
series-parallel treewidth ≤ 2 (branchwidth ≤ 2) | K4 | graph minor | Diestel (2000),[1] p. 327 | |
treewidth ≤ 3 | K5, octahedron, pentagonal prism, Wagner graph | graph minor | [12] | |
branchwidth ≤ 3 | K5, octahedron, cube, Wagner graph | graph minor | [13] | |
Complement-reducible graphs (cographs) | 4-vertex path P4 | induced subgraph | [14] | |
Trivially perfect graphs | 4-vertex path P4 and 4-vertex cycle C4 | induced subgraph | [15] | |
Threshold graphs | 4-vertex path P4, 4-vertex cycle C4, and complement of C4 | induced subgraph | [15] | |
Line graph of 3-uniform linear hypergraphs | a finite list of forbidden induced subgraphs with minimum degree at least 19 | induced subgraph | [16] | |
Line graph of k-uniform linear hypergraphs, k > 3 | a finite list of forbidden induced subgraphs with minimum edge degree at least 2k2 − 3k + 1 | induced subgraph | [17][18] | |
General theorems | ||||
a family defined by an induced-hereditary property | a (not necessarily finite) obstruction set | induced subgraph | ||
a family defined by an minor-hereditary property | a finite obstruction set | graph minor | Robertson–Seymour theorem |
See also
References
- ^ a b c Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, ISBN 0-387-98976-5.
- ^ Gupta, A.; Impagliazzo, R. (1991), "Computing planar intertwines", [[Symposium on Foundations of Computer Science|Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91)]], IEEE Computer Society, pp. 802–811, doi:10.1109/SFCS.1991.185452
{{citation}}
: URL–wikilink conflict (help). - ^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society, 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR 1164063.
- ^ Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9
- ^ Kashiwabara, Toshinobu (1981), "Algorithms for some intersection graphs", in Saito, Nobuji; Nishizeki, Takao (eds.), Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings, Lecture Notes in Computer Science, vol. 108, Springer-Verlag, pp. 171–181, doi:10.1007/3-540-10704-5\_15.
- ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem" (PDF), Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070v1, doi:10.4007/annals.2006.164.51.
- ^ Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J. (eds.), Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.
- ^ El-Mallah, Ehab; Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems, 35 (3): 354–362, doi:10.1109/31.1748.
- ^ Takamizawa, K.; Nishizeki, Takao; Saito, Nobuji (1981), "Combinatorial problems on series-parallel graphs", Discrete Applied Mathematics, 3 (1): 75–76, doi:10.1016/0166-218X(81)90031-7.
- ^ Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), "Linear-Time Recognition of Helly Circular-Arc Models and Graphs", Algorithmica, 59 (2): 215–239, doi:10.1007/s00453-009-9304-5
- ^ Földes, Stéphane; Hammer, Peter L. (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860
- ^ Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4.
- ^ Bodlaender, Hans L.; Thilikos, Dimitrios M. (1999), "Graphs with branchwidth at most three", Journal of Algorithms, 32 (2): 167–194, doi:10.1006/jagm.1999.1011.
- ^ Seinsche, D. (1974), "On a property of the class of n-colorable graphs", Journal of Combinatorial Theory, Series B, 16 (2): 191–193, doi:10.1016/0095-8956(74)90063-X, MR 0337679
- ^ a b Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics, 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4..
- ^ Metelsky, Yury; Tyshkevich, Regina (1997), "On line graphs of linear 3-uniform hypergraphs", Journal of Graph Theory, 25 (4): 243–251, doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K, MR 1459889
- ^ Jacobson, M. S.; Kézdy, Andre E.; Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs", Graphs and Combinatorics, 13: 359–367, MR 1485929
- ^ Naik, Ranjan N.; Rao, S. B.; Shrikhande, S. S.; Singhi, N. M. (1982), "Intersection graphs of k-uniform hypergraphs", European J. Combinatorics, 3: 159–172, MR 0670849