2014/09/02 by Hanna Furmańczyk, Furmańczyk, Hanna, Marek Kubale +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1409.0650
openalex publication_date 2014/09/02 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
A graph is equitably k-colorable if its vertices can be partitioned into\nk independent sets in such a way that the number of vertices in any two sets\ndiffer by at most one. The smallest k for which such a coloring exists is\nknown as the \equitable chromatic number of G and it is denoted by\n\χ=(G). In this paper the problem of determinig \χ_= for coronas of\ncubic graphs is studied. Although the problem of ordinary coloring of coronas\nof cubic graphs is solvable in polynomial time, the problem of equitable\ncoloring becomes NP-hard for these graphs. We provide polynomially solvable\ncases of coronas of cubic graphs and prove the NP-hardness in a general case.\nAs a by-product we obtain a simple linear time algorithm for equitable coloring\nof such graphs which uses \χ_=(G) or \χ_=(G)+1 colors. Our algorithm is\nbest possible, unless P=NP. Consequently, cubical coronas seem to be the only\nknown class of graphs for which equitable coloring is harder than ordinary\ncoloring.\n