Name
Abstract | ||
|---|---|---|
For properties of graphs P 1 and P 2 a vertex ( P 1 , P 2 ) -partition of a graph G is a partition (V 1 ,V 2 ) of V(G) such that each subgraph G[V i ] induced by V i has property P i , i=1,2 . The class of all vertex ( P 1 , P 2 ) -partitionable graphs is denoted by P 1 ∘ P 2 . An additive hereditary property R is reducible if there exist additive hereditary properties P 1 and P 2 such that R = P 1 ∘ P 2 , otherwise it is irreducible. For a given property P a reducible property R is called a minimal reducible bound for P if P ⊆ R and there is no reducible property R ′ satisfying P ⊆ R ′⊂ R . In this paper we give a survey of known reducible bounds and we prove some new minimal reducible bounds for important classes of planar graphs. The connection between our results and Barnette's conjecture is also presented. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0012-365X(99)00205-8 | Discrete Mathematics |
Keywords | Field | DocType |
05c75,planar graph,hereditary,05c15,additive,minimal reducible bound,vertex partition,property of graphs,satisfiability | Has property,Graph,Discrete mathematics,Combinatorics,Hereditary property,Graph property,Vertex (geometry),Partition (number theory),Conjecture,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
212 | 1-2 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.67 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mieczysław Borowiecki | 1 | 62 | 7.76 |
| Izak Broere | 2 | 143 | 31.30 |
| Peter Mihók | 3 | 232 | 44.49 |