Group coloring is \(\Pi_2^{\text{P}}\)-complete

DOI10.1016/j.tcs.2005.09.033zbMath1087.68039DBLPjournals/tcs/Kral05OpenAlexW1995928453WikidataQ57601558 ScholiaQ57601558MaRDI QIDQ817778

Daniel Král'

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.033

zbMATH Keywords

group connectivitynowhere-zero flows

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colorings and orientations of graphs
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• The 4-choosability of plane graphs without 4-cycles
• Every planar graph is 5-choosable
• Group chromatic number of graphs without \(K_5\)-minors
• 3-list-coloring planar graphs of girth 5
• A note on group colorings

This page was built for publication: Group coloring is \(\Pi_2^{\text{P}}\)-complete