On incidence coloring of complete multipartite and semicubic bipartite graphs

DOI10.7151/dmgt.1995zbMath1377.05062OpenAlexW2718014229MaRDI QIDQ1692634

Robert Janczewski, Michał Małafiejski, Anna Małafiejska

Publication date: 10 January 2018

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.1995

zbMATH Keywords

NP-completenesscomplete multipartite graphssubcubic graphsincidence coloring\(L(1,1)\)-labellingsemicubic graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Interval incidence coloring of subcubic graphs ⋮ On incidence choosability of cubic graphs ⋮ Incidence coloring of mycielskians with fast algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Incidence coloring of pseudo-Halin graphs
• Invalid proofs on incidence coloring
• Some results on the incidence coloring number of a graph
• Star arboricity
• 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
• Incidence coloring of \(k\)-degenerated graphs
• Incidence coloring of Cartesian product graphs
• NP-completeness of 4-incidence colorability of semi-cubic graphs
• The incidence chromatic number of some graph

This page was built for publication: On incidence coloring of complete multipartite and semicubic bipartite graphs