Jump to content

Forbidden graph characterization

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 193.48.71.237 (talk) at 14:36, 19 November 2012 (→List of forbidden characterizations for graphs and hypergraphs). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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:

(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

  1. ^ a b c Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, ISBN 0-387-98976-5.
  2. ^ 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).
  3. ^ 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.
  4. ^ Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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
  11. ^ 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
  12. ^ 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.
  13. ^ 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.
  14. ^ 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
  15. ^ a b Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics, 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4..
  16. ^ 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
  17. ^ 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
  18. ^ 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Forbidden_graph_characterization&oldid=523851327"