Geodesic
2-dimensional Convexity Numbers and P 4-free Graphs
Canadian mathematical bulletin, Tome 57 (2014) no. 1, pp. 61-71

Voir la notice de l'article provenant de la source Cambridge University Press

For $S\,\subseteq \,{{\mathbb{R}}^{n}}$ a set $C\,\subseteq \,S$ is an $m$ -clique if the convex hull of no $m$ -element subset of $C$ is contained in $S$ . We show that there is essentially just one way to construct a closed set $S\,\subseteq \,{{\mathbb{R}}^{2}}$ without an uncountable 3-clique that is not the union of countably many convex sets. In particular, all such sets have the same convexity number; that is, they require the same number of convex subsets to cover them. The main result follows from an analysis of the convex structure of closed sets in ${{\mathbb{R}}^{2}}$ without uncountable 3-cliques in terms of clopen, ${{P}_{4}}$ -free graphs on Polish spaces.
DOI : 10.4153/CMB-2012-031-5
Mots-clés : 52A10, 03E17, 03E75, convex cover, convexity number, continuous coloring, perfect graph, cograph 
Geschke, Stefan. 2-dimensional Convexity Numbers and P 4-free Graphs. Canadian mathematical bulletin, Tome 57 (2014) no. 1, pp. 61-71. doi: 10.4153/CMB-2012-031-5
@article{10_4153_CMB_2012_031_5,
     author = {Geschke, Stefan},
     title = {2-dimensional {Convexity} {Numbers} and {P} 4-free {Graphs}},
     journal = {Canadian mathematical bulletin},
     pages = {61--71},
     year = {2014},
     volume = {57},
     number = {1},
     doi = {10.4153/CMB-2012-031-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-2012-031-5/}
}
TY  - JOUR
AU  - Geschke, Stefan
TI  - 2-dimensional Convexity Numbers and P 4-free Graphs
JO  - Canadian mathematical bulletin
PY  - 2014
SP  - 61
EP  - 71
VL  - 57
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-2012-031-5/
DO  - 10.4153/CMB-2012-031-5
ID  - 10_4153_CMB_2012_031_5
ER  - 
%0 Journal Article
%A Geschke, Stefan
%T 2-dimensional Convexity Numbers and P 4-free Graphs
%J Canadian mathematical bulletin
%D 2014
%P 61-71
%V 57
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-2012-031-5/
%R 10.4153/CMB-2012-031-5
%F 10_4153_CMB_2012_031_5

[1] [1] Alon, N., Problems and results in Extremal Combinatorics, Part I. Discrete Math. 273 (2003), 31–53. Google Scholar | DOI

[2] [2] Corneil, D. G., Lerchs, H., and Burlingham, L. S., Complement reducible graphs. Discrete Applied Math. 3 (1981), 163–174. Google Scholar | DOI

[3] [3] Chudnovsky, M., Robertson, N., Seymour, P. D., and Thomas, R., The strong perfect graph theorem. Ann. of Math. 164 (2006), 51–229. Google Scholar | DOI

[4] [4] Geschke, S., A dual open coloring axiom. Ann. Pure Appl. Logic 140 (2006), 40–51. Google Scholar | DOI

[5] [5] Geschke, S., Goldstern, M., and Kojman, M., Continuous Ramsey theory on Polish spaces and coveringthe plane by functions. J. Mathematical Logic 4 (2004), 109–145. Google Scholar | DOI

[6] [6] Geschke, S., Kubiś, W., Kojman, M., and Schipperus, R., Convex decompositions in the plane, meagreideals and continuous pair colorings of the irrationals. Israel J. Math. 131 (2002), 285–317. Google Scholar | DOI

[7] [7] Kojman, M., Perles, M., Shelah, S., Sets in a Euclidean space which are not a countable union of convexsubsets. Israel J. Math. 70 (1990), 313–342. Google Scholar | DOI

[8] [8] Lovász, L., Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2 (1972), 253–267. Google Scholar | DOI

[9] [9] Seinsche, D., On a property of the class of n-colorable graphs. J. Combin. Theory Ser. B 16 (1974), 191–193. Google Scholar | DOI

Cité par Sources :