On the Existence of Specific Stars in Planar Graphs

• Ando, K., Iwasaki, S., Kaneko, A.: Every 3-connected planar graph has a connected subgraph with small degree sum, Annual Meeting of Mathematical Society of Japan (1993) (Japanese)

• Balogh, J., Kochol, M., Pluhár, A., Yu, X.: Covering planar graphs with forests, J. Combin. Theory Ser. B 94, 147–158 (2005)

  Google Scholar 

• Dvořák, Z., Král’, D., Nejedlý, P., Škrekovski, R.: Coloring squares of planar graphs with girth six, European J. Combin. (to appear)

• Enomoto, H., Ota, K.: Connected subgraphs with small degree sum in 3-connected planar graphs, J. Graph Theory 30, 191–203 (1999)

  Google Scholar 

• Fabrici, I., Harant, J., Jendrol’, S.: Paths of low weight in planar graphs, Discuss. Math. Graph Theory (to appear)

• Fabrici, I., Jendrol’, S.: Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs Combin. 13, 245–250 (1997)

  Google Scholar 

• Franklin, P.: The four color problem, Am. J. Math. 44, 225–236 (1922)

  Google Scholar 

• Grünbaum, B.: New views on some old questions of combinatorial geometry, Int. Teorie Combinat. 1, 451–468 (1976)

  Google Scholar 

• van den Heuvel, J., McGuinness, S.: Coloring the square of a planar graph, J. Graph Theory 42, 110–124 (2003)

  Google Scholar 

• Ivančo, J.: The weight of a graph, Ann. Discrete Math. 51 113–116 (1992)

  Google Scholar 

• Jendrol’, S.: Paths with restricted degrees of their vertices in planar graphs, Czechoslovak Math. J. 49(124), 481–490 (1999)

  Google Scholar 

• Jendrol’, S., Madaras, T.: On light subgraphs in plane graphs of minimum degree five, Discuss. Math. Graph Theory 16, 207–217 (1996)

  Google Scholar 

• Jendrol’, S., Madaras, T.: Note on an existence of small degree vertices with at most one big degree neighbour in planar graph, Tatra Mt. Math. Publ. 30, 1–5 (2004)

  Google Scholar 

• Jendrol’, S., Schiermeyer, I.: On max-min problem concerning weights of edges, Combinatorica 21, 351–359 (2001)

  Google Scholar 

• Jensen, T.R., Toft, B.: Graph Coloring Problems, Wiley, New York, 1995

• Jendrol’, S., Tuhársky, M.: A Kotzig type theorem for non orientable surfaces, Math. Slovaca 56, 245–253 (2006)

  Google Scholar 

• Jendrol’, S., Voss, H.-J.: Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristics ≤ 0 – a survey, In: Paul Erdős and his Mathematics (G. Halász, L. Lovász, M. Simonovits, V.T. Sós eds.), Bolyai Society Mathematical Studies, Vol. 11, Budapest, 2002

• Jendrol’, S., Voss, H.-J.: Light subgraphs of graphs embedded in the plane and in the projective plane – a survey, Discrete Math. (submitted)

• Kotzig, A.: Contribution to the theory of Eulerian polyhedra, Mat. Čas. SAV (Math. Slovaca) 5, 101–113 (1955)

• Kotzig, A.: Extremal polyhedral graphs, Ann. New York Acad. Sci. 319, 565–570 (1979)

• Lebesgue, H.: Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19, 27–43 (1940)

  Google Scholar 

• Mohar, B.: Light paths in 4-connected graphs in the plane and other surfaces, J. Graph Theory 34, 170–179 (2000)

  Google Scholar 

• Molloy, M., Salavatipour, M.R.: A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B 94, 189–213 (2005)

  Google Scholar 

• Wegner, G.: Graphs with given diameter and a colouring problem (1977), Preprint, University of Dortmund

• Wernicke, P.: Über den kartographischen Vierfarbensatz, Math. Ann. 58, 413–426 (1904)

  Google Scholar 

Download references