Geometric achromatic and pseudoachromatic indices. (English) Zbl 1339.05105
Summary: The pseudoachromatic index of a graph is the maximum number of colors that can be assigned to its edges, such that each pair of different colors is incident to a common vertex. If for each vertex its incident edges have different color, then this maximum is known as achromatic index. Both indices have been widely studied. A geometric graph is a graph drawn in the plane such that its vertices are points in general position, and its edges are straight-line segments. In this paper we extend the notion of pseudoachromatic and achromatic indices for geometric graphs, and present results for complete geometric graphs. In particular, we show that for \(n\) points in convex position the achromatic index and the pseudoachromatic index of the complete geometric graph are \(\lfloor \frac{n^2+n}{4} \rfloor\).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Ábrego, B.M., Cetina, M., Fernández-Merchant, S., Leaños, J., Salazar, G.: 3-symmetric and 3-decomposable geometric drawings of \[K_n\] Kn. Discrete Appl. Math. 158(12), 1240-1458 (2010) · Zbl 1228.05214 · doi:10.1016/j.dam.2009.09.020 |
| [2] | Araujo-Pardo, G., Dumitrescu, A., Hurtado, F., Noy, M., Urrutia, J.: On the chromatic number of some geometric type Kneser graphs. Comput. Geom. 32(1), 59-69 (2005) · Zbl 1067.05023 · doi:10.1016/j.comgeo.2004.10.003 |
| [3] | Araujo-Pardo, G., Montellano-Ballesteros, J.J., Strausz, R.: On the pseudoachromatic index of the complete graph. J. Graph Theory 66(2), 89-97 (2011) · Zbl 1238.05081 · doi:10.1002/jgt.20491 |
| [4] | Araujo-Pardo, G., Montellano-Ballesteros, J.J., Strausz, R., Rubio-Montiel, C.: On the pseudoachromatic index of the complete graph II. Bol. Soc. Mat. Mex. 20(1), 17-28 (2014) · Zbl 1306.05048 · doi:10.1007/s40590-014-0007-9 |
| [5] | Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993) · Zbl 0284.05101 |
| [6] | Bouchet, A.: Indice achromatique des graphes multiparti complets et réguliers. Cahiers Centre Études Rech. Opér. 20(3-4), 331-340 (1978) · Zbl 0404.05026 |
| [7] | Cairnie, N., Edwards, K.: Some results on the achromatic number. J. Graph Theory 26(3), 129-136 (1997) · Zbl 0884.05043 · doi:10.1002/(SICI)1097-0118(199711)26:3<129::AID-JGT3>3.0.CO;2-T |
| [8] | Ceder, J.G.: Generalized sixpartite problems. Bol. Soc. Mat. Mex. 2(9), 28-32 (1964) · Zbl 0158.19802 |
| [9] | Chartrand, G., Zhang, p: Chromatic Graph Theory. Discrete Mathematics and its Applications. CRC Press, Boca Raton (2009) · Zbl 1169.05001 |
| [10] | Dujmovic, V., Wood, D.R.: Thickness and antithickness. 2010, in preparation · Zbl 1423.68335 |
| [11] | Edwards, K.: The complexity of harmonious colouring for trees. Discrete Appl. Math. 57(23), 133-144 (1995). Combinatorial optimization 1992 · Zbl 0816.05026 · doi:10.1016/0166-218X(94)00100-R |
| [12] | Erdős, P.: On sets of distances of \[n\] n points. Am. Math. Mon. 53, 248-250 (1946) · Zbl 0060.34805 · doi:10.2307/2305092 |
| [13] | Fabila-Monroy, R., Wood, D.R.: The Chromatic Number of the Convex Segment Disjointness Graph. Computational Geometry, pp. 79-84. Springer, Berlin (2012) · Zbl 1375.68131 |
| [14] | Fáry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229-233 (1948) · Zbl 0030.17902 |
| [15] | Open Problem Garden: Edge-colouring geometric complete graphs (2015) [accessed 16-Jan 2015] |
| [16] | Godsil, C.D., Royle, G.: Algebraic Graph Theory, vol. 207. Springer, New York (2001) · Zbl 0968.05002 |
| [17] | Gupta, R.P.: Bounds on the chromatic and achromatic numbers of complementary graphs. Recent progress in combinatorics. In: Proceedings of Third Waterloo Conference on Comb., pp. 229-235. Academic Press, New York (1968) · Zbl 0060.34805 |
| [18] | Harary, F., Hedetniemi, S., Prins, G.: An interpolation theorem for graphical homomorphisms. Portugal. Math. 26, 453-462 (1967) · Zbl 0187.20903 |
| [19] | Hell, P., Miller, D.J.: Graph with given achromatic number. Discrete Math. 16(3), 195-207 (1976) · Zbl 0345.05113 · doi:10.1016/0012-365X(76)90099-6 |
| [20] | Jonsson, J.: The exact chromatic number of the convex segment disjointness graph (2011) · Zbl 0345.05113 |
| [21] | Lovász, L., Pach, J., Szegedy, M.: On Conway’s thrackle conjecture. Discrete Comput. Geom. 18(4), 369-376 (1997) · Zbl 0892.05017 · doi:10.1007/PL00009322 |
| [22] | Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364-372 (1980) · Zbl 0455.05047 · doi:10.1137/0138030 |
| [23] | Yegnanarayanan, V.: The pseudoachromatic number of a graph. Southeast Asian Bull. Math. 24(1), 129-136 (2000) · Zbl 0959.05043 · doi:10.1007/s10012-000-0129-z |
| [24] | Yegnanarayanan, V.: Graph colourings and partitions. Theor. Comput. Sci. 263(12), 59-74 (2001). Combinatorics and Computer Science · Zbl 0979.68065 · doi:10.1016/S0304-3975(00)00231-0 |
| [25] | Zaker, M.: Results on the grundy chromatic number of graphs. Discrete mathematics 306(23), pp. 3166-3173 (2006), International workshop on combinatorics, linear algebra, and graph coloring · Zbl 1105.05027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
