Star coloring of subcubic graphs | Zendy

T. Karthick | Zendy; C. R. Subramanian | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Star coloring of subcubic graphs

Author(s) -

T. Karthick,

C. R. Subramanian

Publication year - 2013

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.1672

Subject(s) - combinatorics , mathematics , list coloring , fractional coloring , edge coloring , complete coloring , graph , star (game theory) , discrete mathematics , graph power , line graph , mathematical analysis

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research