# Vertex coloring the square of outerplanar graphs of low degree

Geir Agnarsson; Magnús M. Halldórsson

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 4, page 619-636
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGeir Agnarsson, and Magnús M. Halldórsson. "Vertex coloring the square of outerplanar graphs of low degree." Discussiones Mathematicae Graph Theory 30.4 (2010): 619-636. <http://eudml.org/doc/271020>.

@article{GeirAgnarsson2010,

abstract = {Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.},

author = {Geir Agnarsson, Magnús M. Halldórsson},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {outerplanar; chromatic number; power of a graph; weak dual},

language = {eng},

number = {4},

pages = {619-636},

title = {Vertex coloring the square of outerplanar graphs of low degree},

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

volume = {30},

year = {2010},

}

TY - JOUR

AU - Geir Agnarsson

AU - Magnús M. Halldórsson

TI - Vertex coloring the square of outerplanar graphs of low degree

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 4

SP - 619

EP - 636

AB - Vertex colorings of the square of an outerplanar graph have received a lot of attention recently. In this article we prove that the chromatic number of the square of an outerplanar graph of maximum degree Δ = 6 is 7. The optimal upper bound for the chromatic number of the square of an outerplanar graph of maximum degree Δ ≠ 6 is known. Hence, this mentioned chromatic number of 7 is the last and only unknown upper bound of the chromatic number in terms of Δ.

LA - eng

KW - outerplanar; chromatic number; power of a graph; weak dual

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

ER -

## References

top- [1] G. Wegner, Graphs with given diameter and a coloring problem (Technical report, University of Dortmund, 1977).
- [2] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley Interscience, 1995). http://www.imada.sdu.dk/Research/Graphcol/. Zbl0855.05054
- [3] M. Molloy and M.R. Salavatipour, A bound on the chromatic number of the square of a planar graph, J. Combin. Theory (B) 94 (2005) 189-213, doi: 10.1016/j.jctb.2004.12.005. Zbl1071.05036
- [4] G. Agnarsson and M.M. Halldórsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651-662, doi: 10.1137/S0895480100367950. Zbl1029.05047
- [5] O. Borodin, H.J. Broersma, A. Glebov and J. van den Heuvel, Stars and bunches in planar graphs. Part II: General planar graphs and colorings. CDAM Research Report Series 2002-05, (2002).
- [6] J. van den Heuvel and S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42 (2003) 110-124, doi: 10.1002/jgt.10077. Zbl1008.05065
- [7] K.-W. Lih, W.-F. Wang and X. Zhu, Coloring the square of a K₄-minor free graph, Discrete Math. 269 (2003) 303-309, doi: 10.1016/S0012-365X(03)00059-1. Zbl1027.05042
- [8] T. Calamoneri and R. Petreschi, L(h,1)-labeling subclasses of planar graphs, J. Parallel and Distributed Computing 64 (2004) 414-426, doi: 10.1016/j.jpdc.2003.11.005. Zbl1084.68089
- [9] G. Agnarsson and M.M. Halldórsson, On Colorings of Squares of Outerplanar Graphs, in: Proceedings of the Fifteenth Annual ACM-SIAM Symposium On Discrete Algorithms (SODA 2004), (New Orleans, 2004) 237-246. Zbl1318.05022
- [10] G. Agnarsson and M.M. Halldórsson, On Colorings of Squares of Outerplanar Graphs, arXiv:0706.1526v1 [math.CO]. Zbl1318.05022
- [11] K.-W. Lih and W.-F. Wang, Coloring the square of an outerplanar graph, Taiwanese J. Math. 10 (2006) 1015-1023. Zbl1135.05022
- [12] X. Luo, Chromatic number of square of maximal outerplanar graphs, Appl. Math. J. Chinese Univ. (B) 22 (2007) 163-168, doi: 10.1007/s11766-007-0204-7. Zbl1136.05020
- [13] N. Lin, Coloring the square of outerplanar graphs, J. Nanjing Norm. Univ. Nat. Sci. Ed. 27 (2004) 28-31. Zbl1160.05318
- [14] L.Z. Liu, Z.F. Zhang and J.F. Wang, The adjacent strong edge chromatic number of outerplanar graphs with Δ(G) ≤ 4, Appl. Math. J. Chinese Univ. (A) 15 (2000) 139-146. Zbl0993.05074
- [15] W.C. Shiu, P. Che Bor Lam and Z. Zhang, Entire chromatic number of maximal outerplanar graphs with maximum degree at most 4, in: Combinatorics, Graph Theory, and Algorithms, Vol. I, II (Kalamazoo, MI, 1996), 591-595 (New Issues Press, Kalamazoo, MI, 1999).
- [16] N. Wang and Z. Zhang, On the complete chromatic number of maximum outerplanar graphs with maximum degree Δ = 6, Pure Appl. Math. (Xi'an) 12 (1996) 68-72. Zbl0864.05038
- [17] C.F. Chang, J.X. Chang, X.C. Lu, Peter C.B. Lam and J.F. Wang, Edge-face total chromatic number of outerplanar graphs with Δ(G) = 6, in: Computing and Combinatorics (Xi'an, 1995), Lecture Notes in Comput. Sci. 959 (Springer, Berlin, 1995), 396-399.
- [18] N.S. Wang, Z.F. Zhang and Y.Y. Zhou, Edge-face entire chromatic numbers of maximal outerplanar graphs, Pure Appl. Math. (Xi'an) 10 (1994) 11-16. Zbl0842.05035
- [19] D.B. West, Introduction to Graph Theory, Prentice-Hall Inc., Upper Saddle River (New Jersey, 2nd ed., 2001).

## NotesEmbed ?

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