# Uniquely partitionable graphs

Jozef Bucko; Marietjie Frick; Peter Mihók; Roman Vasky

Discussiones Mathematicae Graph Theory (1997)

- Volume: 17, Issue: 1, page 103-113
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJozef Bucko, et al. "Uniquely partitionable graphs." Discussiones Mathematicae Graph Theory 17.1 (1997): 103-113. <http://eudml.org/doc/270374>.

@article{JozefBucko1997,

abstract = {Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G[V_i]$ induced by $V_i$ has property $_i$; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property , then we say that is additive. A property is called degenerate if there exists a bipartite graph that does not have property . In this paper, we prove that if ₁,..., ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (₁,...,ₙ)-partitionable graph.},

author = {Jozef Bucko, Marietjie Frick, Peter Mihók, Roman Vasky},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary property of graphs; additivity; reducibility; vertex partition; partition; hereditary properties of graphs},

language = {eng},

number = {1},

pages = {103-113},

title = {Uniquely partitionable graphs},

url = {http://eudml.org/doc/270374},

volume = {17},

year = {1997},

}

TY - JOUR

AU - Jozef Bucko

AU - Marietjie Frick

AU - Peter Mihók

AU - Roman Vasky

TI - Uniquely partitionable graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1997

VL - 17

IS - 1

SP - 103

EP - 113

AB - Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G[V_i]$ induced by $V_i$ has property $_i$; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property , then we say that is additive. A property is called degenerate if there exists a bipartite graph that does not have property . In this paper, we prove that if ₁,..., ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (₁,...,ₙ)-partitionable graph.

LA - eng

KW - hereditary property of graphs; additivity; reducibility; vertex partition; partition; hereditary properties of graphs

UR - http://eudml.org/doc/270374

ER -

## References

top- [1] J.A. Andrews and M.S. Jacobson, On a generalization of chromatic number, Congressus Numerantium 47 (1985) 33-48.
- [2] G. Benadé, I. Broere and J.I. Brown, A construction of uniquely C₄-free colourable graphs, Questiones Mathematicae 13 (1990) 259-264, doi: 10.1080/16073606.1990.9631616. Zbl0725.05042
- [3] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely ${(m,k)}^{\tau}$-colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22, doi: 10.1016/0012-365X(95)00301-C. Zbl0870.05026
- [4] B. Bollobás and N. Sauer, Uniquely colourable graphs with large girth, Canad. J. Math. 28 (1976) 1340-1344, doi: 10.4153/CJM-1976-133-5. Zbl0344.05115
- [5] B. Bollobás and A.G. Thomason, Uniquely partitionable graphs, J. London Math. Soc. 16 (1977) 403-410, doi: 10.1112/jlms/s2-16.3.403. Zbl0377.05038
- [6] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, eds., Advances in Graph Theory, (Vishwa International Publication, Gulbarga 1991) 42-69.
- [7] I. Broere and M. Frick, On the order of uniquely (k,m)-colourable graphs, Discrete Math. 82 (1990) 225-232, doi: 10.1016/0012-365X(90)90200-2. Zbl0712.05024
- [8] J.I. Brown and D.G. Corneil, On generalized graph colourings, J. Graph Theory 11 (1987) 86-99, doi: 10.1002/jgt.3190110113.
- [9] J.I. Brown, D. Kelly, J. Schoenheim and R.E. Woodrow, Graph coloring satisfying restraints, Discrete Math. (1990) 123-143, doi: 10.1016/0012-365X(90)90113-V. Zbl0696.05024
- [10] S.A. Burr and M.S. Jacobson, On inequalities involving vertex-partition parameters of graphs, Congressus Numerantium 70 (1990) 159-170. Zbl0697.05046
- [11] L.J. Cowen, R.H. Cowen and D.R. Woodall, Defective colorings of graphs in surfaces; partitions into subgraphs of bounded valency, J. Graph Theory 10 (1986) 187-195, doi: 10.1002/jgt.3190100207. Zbl0596.05024
- [12] M. Frick, A survey of (m,k)-colourings, in: J. Gimbel c.a, eds., Quo Vadis,Graph Theory? Annals of Discrete Mathematics 55 (North-Holland, Amsterdam, 1993) 45-58.
- [13] M. Frick and M.A. Henning, Extremal results on defective colorings of graph, Discrete Math. 126 (1994) 151-158, doi: 10.1016/0012-365X(94)90260-7. Zbl0794.05029
- [14] D. Gernet, Forbidden and unavoidable subgraphs, Ars Combinatoria 27 (1989) 165-176. Zbl0673.05047
- [15] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V., Amsterdam 1995). Zbl0833.05001
- [16] D.L. Greenwell, R.L. Hemminger and J. Klerlein, Forbidden subgraphs, in: Proc. 4th S-E Conf. Combinatorics, Graph Theory and Computing, (Utilitas Math., Winnipeg, Man., 1973) 389-394. Zbl0312.05128
- [17] F. Harary, S.T. Hedetniemi and R.W. Robinson, Uniquely colourable graphs, J. Combin. Theory 6 (1969) 264-270, doi: 10.1016/S0021-9800(69)80086-4. Zbl0175.50205
- [18] G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory (B) 10 (1971) 12-41, doi: 10.1016/0095-8956(71)90065-7. Zbl0223.05101
- [19] G. Chartrand and J.P. Geller, Uniquely colourable planar graphs, J. Combin. Theory 6 (1969) 271-278, doi: 10.1016/S0021-9800(69)80087-6. Zbl0175.50206
- [20] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York 1995).
- [21] R.P. Jones, Hereditary properties and P-chromatic number, in: T.P. McDonough and V.C. Marron, eds., Combinatorics, Proc. Brit. Comb. Conf. (London Math. Soc. Lecture Note Ser., No.13, Cambridge Univ. Press, London 1974) 83-88.
- [22] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238. Zbl0151.33401
- [23] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
- [24] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106. Zbl0348.05109
- [25] F.S. Roberts, From garbage to rainbows: generalizations of graph colouring and their applications, in: Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk, eds., Graph Theory, Combinatorics and Applications, (Wiley, New York, 1991) 1031-1052. Zbl0841.05033
- [26] F.S. Roberts, New directions in graph theory (with an emphasis on the role of applications), in: J. Gimbel, J.W. Kennedy, and L.V. Quintas, eds., Quo Vadis Graph Theory, (North-Holland, Amsterdam, 1993) 13-44. Zbl0787.05089
- [27] J.M.S. Simoes-Pereira, Joins of n-degenerate graphs and uniquely (m,n)-partitionable graphs, J. Combin. Theory (B) 21 (1976) 21-29, doi: 10.1016/0095-8956(76)90023-X. Zbl0336.05107
- [28] J.M.S. Simoes-Pereira, On graphs uniquely partitionable into n-degenerate subgraphs, in: Infinite and Finite Sets Colloquia Math. Soc. J. Bólyai 10 (North-Holland, Amsterdam, 1975) 1351-1364.
- [29] M. Simonovits, Extremal graph theory, in: L.W. Beineke and R.J. Wilson, eds., Selected Topics in Graph Theory, 2 (Academic Press, London, 1983) 161-200.
- [30] M. Simonovits, Extremal graph problems and graph products, in: Studies in Pure Math. (dedicated to the memory of P. Turán) (1983) 669-680.
- [31] M. Weaver and D.B. West, Relaxed chromatic numbers of graphs, Graphs and Combinatorics 10 (1994) 75-93, doi: 10.1007/BF01202473. Zbl0796.05036
- [32] D. Woodall, Improper colorings of graphs, in: R. Nelson and R.J. Wilson, eds., Graph Colorings (Longman, New York, 1990) 45-64.
- [33] X. Zhu, Uniquely H-colorable graphs with large girth, J. Graph Theory 23 (1996) 33-41, doi: 10.1002/(SICI)1097-0118(199609)23:1<33::AID-JGT3>3.0.CO;2-L Zbl0864.05037

## Citations in EuDML Documents

top- Jan Kratochvíl, Ingo Schiermeyer, On the computational complexity of (O,P)-partition problems
- Jozef Bucko, Jaroslav Ivančo, Uniquely partitionable planar graphs with respect to properties having a forbidden tree
- Jenő Szigeti, Zsolt Tuza, Generalized colorings and avoidable orientations
- Mieczysław Borowiecki, Peter Mihók, Zsolt Tuza, M. Voigt, Remarks on the existence of uniquely partitionable planar graphs
- Jozef Bucko, Peter Mihók, On infinite uniquely partitionable graphs and graph properties of finite character
- Izak Broere, Jozef Bucko, Peter Mihók, Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.