PDF
Discussiones Mathematicae Graph Theory 30(3) (2010)
393-405
DOI: https://doi.org/10.7151/dmgt.1502
3-CONSECUTIVE C-COLORINGS OF GRAPHS
Csilla Bujtás1, E. Sampathkumar2, Zsolt Tuza1,3, M.S. Subramanya2 and Charles Dominic2
1Department of Computer Science
University of Pannonia
H-8200 Veszprém, Egyetem u. 10, Hungary
2Department of Mathematics
University of Mysore, Mysore, India
3Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
Abstract
A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V→ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number [￣(χ)]3CC(G) of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with [￣(χ)]3CC(G) ≥ k for k = 3 and k = 4.Keywords: graph coloring, vertex coloring, consecutive coloring, upper chromatic number.
2010 Mathematics Subject Classification: 05C15, 05C75.
References
| [1] | C. Berge, Hypergraphs (North-Holland, 1989). |
| [2] | Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, I: General results, Discrete Math. 309 (2009) 4890-4902, doi: 10.1016/j.disc.2008.04.019. |
| [3] | Cs. Bujtás and Zs. Tuza, Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees, Discrete Math. in print, doi:10.1016/j.disc.2008.10.023 |
| [4] | G.J. Chang, M. Farber and Zs. Tuza, Algorithmic aspects of neighborhood numbers, SIAM J. Discrete Math. 6 (1993) 24-29, doi: 10.1137/0406002. |
| [5] | S. Hedetniemi and R. Laskar, Connected domination in graphs, in: Graph Theory and Combinatorics, B. Bollobás, Ed. (Academic Press, London, 1984) 209-218. |
| [6] | J. Lehel and Zs. Tuza, Neighborhood perfect graphs, Discrete Math. 61 (1986) 93-101, doi: 10.1016/0012-365X(86)90031-2. |
| [7] | E. Sampathkumar, DST Project Report, No.SR/S4/MS.275/05. |
| [8] | E. Sampathkumar, M.S. Subramanya and C. Dominic, 3-Consecutive vertex coloring of a graph, Proc. Int. Conf. ICDM (University of Mysore, India, 2008) 147-151. |
| [9] | E. Sampathkumar and P.S. Neralagi, The neighourhood number of a graph, Indian J. Pure Appl. Math. 16 (1985) 126-132. |
| [10] | E. Sampathkumar and H.B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979) 607-613. |
| [11] | F. Sterboul, A new combinatorial parameter, in: Infinite and Finite Sets (A. Hajnal et al., Eds.), Colloq. Math. Soc. J. Bolyai, 10, Keszthely 1973 (North-Holland/American Elsevier, 1975) Vol. III pp. 1387-1404. |
| [12] | V. Voloshin, The mixed hypergraphs, Computer Sci. J. Moldova 1 (1993) 45-52. |
Received 15 May 2009
Revised 19 August 2009
Accepted 24 August 2009
Close