NP-completeness of 4-incidence colorability of semi-cubic graphs

DOI10.1016/j.disc.2007.03.076zbMath1131.05041arXivmath/0607071OpenAlexW2031725292WikidataQ60060539 ScholiaQ60060539MaRDI QIDQ2470012

Jian-hua Tu, Xue Liang Li

Publication date: 11 February 2008

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

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

zbMATH Keywords

NP-completeincidence coloring number\(k\)-incidence colorablesemi-cubic graphstrong-vertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Facial incidence colorings of embedded multigraphs ⋮ On incidence coloring of complete multipartite and semicubic bipartite graphs ⋮ Hypergraph incidence coloring ⋮ Interval incidence coloring of subcubic graphs ⋮ On incidence choosability of cubic graphs ⋮ Incidence coloring of pseudo-Halin graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Incidence and strong edge colorings of graphs
• On incidence coloring and star arboricity of graphs
• On incidence coloring for some cubic graphs
• The incidence coloring conjecture for graphs of maximum degree 3
• The star arboricity of graphs

This page was built for publication: NP-completeness of 4-incidence colorability of semi-cubic graphs