Group coloring is _2P-complete

DOI10.1016/J.TCS.2005.09.033MaRDI QIDQ817778zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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)

Recommendations

• Mathematical Foundations of Computer Science 2004
• Hajós-like theorem for group coloring
• scientific article; zbMATH DE number 4099331
• A note on group colorings
• Group colorability of multigraphs
• A note on group colorings and group structure
• \([1,1,2]\)-colorings of complete graphs
• scientific article; zbMATH DE number 1472119
• A dual version of the brooks group coloring theorem
• A coloring property for countable groups

Cites work

• 3-list-coloring planar graphs of girth 5
• A note on group colorings
• Colorings and orientations of graphs
• Every planar graph is 5-choosable
• Group chromatic number of graphs without \(K_5\)-minors
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 978847 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• scientific article; zbMATH DE number 2188403 (Why is no real title available?)
• The 4-choosability of plane graphs without 4-cycles

Cited in

(2)

• Mathematical Foundations of Computer Science 2004
• On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817778)