Geodesic
Star Coloring Outerplanar Bipartite Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 899-908.

Voir la notice de l'article provenant de la source Library of Science

A proper coloring of the vertices of a graph is called a star coloring if at least three colors are used on every 4-vertex path. We show that all outerplanar bipartite graphs can be star colored using only five colors and construct the smallest known example that requires five colors.
Keywords: chromatic number, star coloring, outerplanar bipartite graph 
@article{DMGT_2019_39_4_a10,
     author = {Ramamurthi, Radhika and Sanders, Gina},
     title = {Star {Coloring} {Outerplanar} {Bipartite} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {899--908},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a10/}
}
TY  - JOUR
AU  - Ramamurthi, Radhika
AU  - Sanders, Gina
TI  - Star Coloring Outerplanar Bipartite Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 899
EP  - 908
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a10/
LA  - en
ID  - DMGT_2019_39_4_a10
ER  - 
%0 Journal Article
%A Ramamurthi, Radhika
%A Sanders, Gina
%T Star Coloring Outerplanar Bipartite Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 899-908
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a10/
%G en
%F DMGT_2019_39_4_a10
Ramamurthi, Radhika; Sanders, Gina. Star Coloring Outerplanar Bipartite Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 899-908. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a10/

[1] M.O. Albertson, G.C. Chappell, H.A. Kierstead, A. Kündgen and R. Ramamurthi, Coloring with no 2 -colored P4’s, Electron. J. Combin. 11 (2004) #R26.

[2] O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211–236. doi:10.1016/0012-365X(79)90077-3

[3] M. Chen, A. Raspaud and W. Wang, 6 -star-coloring of subcubic graphs, J. Graph Theory 72 (2013) 128–145. doi:10.1002/jgt.21636

[4] G. Fertin, A. Raspaud and B. Reed, Star coloring of graphs, J. Graph Theory 47 (2004) 163–182. doi:10.1002/jgt.20029

[5] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390–408. doi:10.1007/BF02764716

[6] H.A. Kierstead, A. Kündgen and C. Timmons, Star coloring bipartite planar graphs, J. Graph Theory 60 (2009) 1–10. doi:10.1002/jgt.20342

[7] J. Nešetřil and P. Ossona de Mendez, Colorings and homomorphisms of minor closed classes, in: B. Aronov, S. Basu, J. Pach and M. Sharir (Eds.), Discrete and Computational Geometry: The Goodman-Pollack Festschrift (Springer-Verlag, Berlin, 2003) 651–664. doi:10.1007/978-3-642-55566-4

[8] G. Sanders, Star Coloring of Outerplanar Bipartite Graphs, M.Sc. Thesis (California State University San Marcos, 2005).

[9] C. Timmons, Star Coloring Planar Graphs, M.Sc. Thesis (California State University San Marcos, 2007).

[10] D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, 2001).