Complexity of conditional colorability of graphs

DOI10.1016/J.AML.2008.04.003MaRDI QIDQ1003864zbMATH OpenOpenAlexFDO

Authors Xiangmei Yao, Wenli Zhou, Xueliang Li, Hajo Broersma

Publication date 4 March 2009

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aml.2008.04.003

zbMATH Keywords

(Conditional) chromatic number\(NP\)-completealgorithmcomplexityconditional coloringvertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Conditional colorings of graphs
• scientific article; zbMATH DE number 3979083
• The 2nd-order conditional 3-coloring of claw-free graphs
• Complexity of conditional colourings with given template
• scientific article; zbMATH DE number 3885934

Cites work

• Conditional colorings of graphs
• Graph theory
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2197944 (Why is no real title available?)
• Some simplified NP-complete graph problems
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(35)

• The complexity of \(G\)-free colourability
• List r-hued chromatic number of graphs with bounded maximum average degrees
• Upper bounds of r-hued colorings of planar graphs
• 3-dynamic coloring and list 3-dynamic coloring of \(K_{1, 3}\)-free graphs
• \(r\)-dynamic chromatic number of extended neighborhood corona of complete graph with some graphs
• Graph \(r\)-hued colorings -- a survey
• On the complexity of cd-coloring of graphs
• On dynamic coloring of certain cycle-related graphs
• \(r\)-Dynamic chromatic number of some line graphs
• On \(r\)-hued colorings of graphs without short induced paths
• Conditional colorings of graphs
• Element deletion changes in dynamic coloring of graphs
• Several sufficient conditions of a normal graph in conditional coloring
• scientific article; zbMATH DE number 3885934 (Why is no real title available?)
• Conditional Hardness for Approximate Coloring
• scientific article; zbMATH DE number 3979083 (Why is no real title available?)
• scientific article; zbMATH DE number 4024813 (Why is no real title available?)
• On r-hued coloring of K₄-minor free graphs
• scientific article; zbMATH DE number 1303029 (Why is no real title available?)
• On the difference between chromatic number and dynamic chromatic number of graphs
• Linear list r-hued coloring of sparse graphs
• -dynamic chromatic number of helm graph families
• On r-dynamic coloring of double star graph families
• On r− dynamic coloring of the gear graph families
• Complexity of conditional colourings with given template
• On \(r\)-dynamic coloring of the total graphs of gear graphs
• On r- dynamic coloring of the family of bistar graphs
• Dynamic coloring on restricted graph classes
• Optimal secret share distribution in degree splitting communication networks
• The list \(r\)-hued coloring of \(K_{m, n}\)
• The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs
• Dynamic coloring on restricted graph classes
• Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number
• On \(r\)-hued coloring of planar graphs with girth at least 6
• The 2nd-order conditional 3-coloring of claw-free graphs

This page was built for publication: Complexity of conditional colorability of graphs

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