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

Abstract

top
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.

How to cite

top

Jozef 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. [1] J.A. Andrews and M.S. Jacobson, On a generalization of chromatic number, Congressus Numerantium 47 (1985) 33-48. 
  2. [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. [3] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely ( m , k ) τ -colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22, doi: 10.1016/0012-365X(95)00301-C. Zbl0870.05026
  4. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [14] D. Gernet, Forbidden and unavoidable subgraphs, Ars Combinatoria 27 (1989) 165-176. Zbl0673.05047
  15. [15] R.L. Graham, M. Grötschel and L. Lovász, Handbook of Combinatorics (Elsevier Science B.V., Amsterdam 1995). Zbl0833.05001
  16. [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. [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. [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. [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. [20] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York 1995). 
  21. [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. [22] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238. Zbl0151.33401
  23. [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. [24] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106. Zbl0348.05109
  25. [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. [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. [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. [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. [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. [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. [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. [32] D. Woodall, Improper colorings of graphs, in: R. Nelson and R.J. Wilson, eds., Graph Colorings (Longman, New York, 1990) 45-64. 
  33. [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
  1. Jan Kratochvíl, Ingo Schiermeyer, On the computational complexity of (O,P)-partition problems
  2. Jozef Bucko, Jaroslav Ivančo, Uniquely partitionable planar graphs with respect to properties having a forbidden tree
  3. Jenő Szigeti, Zsolt Tuza, Generalized colorings and avoidable orientations
  4. Mieczysław Borowiecki, Peter Mihók, Zsolt Tuza, M. Voigt, Remarks on the existence of uniquely partitionable planar graphs
  5. Jozef Bucko, Peter Mihók, On infinite uniquely partitionable graphs and graph properties of finite character
  6. Izak Broere, Jozef Bucko, Peter Mihók, Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.