Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs

DOI10.1016/j.dam.2017.12.002zbMath1380.05062arXiv1606.06333OpenAlexW2962902234MaRDI QIDQ1701101

Marek Kubale, Hanna Furmańczyk

Publication date: 22 February 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.06333

zbMATH Keywords

cubic graphsequitable coloringsubcubic graphssemi-equitable coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Equitable \(\Delta\)-coloring of graphs
• A fast algorithm for equitable coloring
• Some simplified NP-complete graph problems
• Equitable coloring and the maximum degree
• Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
• Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
• On the independence number of random cubic graphs
• Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

This page was built for publication: Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs