Open AccessStar coloring outerplanar bipartite graphs
Author(s) -
Radhika Ramamurthi,
Gina M. Sanders
Publication year - 2018
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2109
Subject(s) - mathematics , combinatorics , bipartite graph , star (game theory) , outerplanar graph , partial k tree , edge coloring , dense graph , 1 planar graph , discrete mathematics , pathwidth , chordal graph , graph , line graph , graph power , mathematical analysis
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom