List-coloring clique-hypergraphs of K₅-minor-free graphs strongly

DOI10.1016/J.DISC.2019.111777MaRDI QIDQ2297730zbMATH OpenOpenAlexFDO

Authors Zuosong Liang, Erfang Shan, Jian-Liang Wu

Publication date 20 February 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2019.111777

zbMATH Keywords

\( K_5\)-minorclique hypergraphlinear-time algorithmlist coloringplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Hypergraphs (05C65)

Recommendations

• Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)
• List-coloring graphs without \(K_{4,k}\)-minors
• The Grötzsch theorem for the hypergraph of maximal cliques
• Choosability of K₅-minor-free graphs
• List-color-critical graphs on a fixed surface

Cites work

• A linear-time algorithm for clique-coloring planar graphs
• A linear-time algorithm for clique-coloring problem in circular-arc graphs
• Algorithmic complexity of list colorings
• Chains, antichains, and fibres
• Clique coloring \(B_1\)-EPG graphs
• Clique-coloring claw-free graphs
• Clique-coloring some classes of odd-hole-free graphs
• Clique-transversal sets and clique-coloring in planar graphs
• Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)
• Coloring the cliques of line graphs
• Coloring the Maximal Cliques of Graphs
• Complexity of clique coloring and related problems
• Complexity of clique-coloring odd-hole-free graphs
• Decomposing and clique-coloring (diamond, odd-hole)-free graphs
• Fibres and ordered set coloring
• On the complexity of bicoloring clique hypergraphs of graphs
• On the divisibility of graphs
• Perfect graphs of arbitrarily large clique-chromatic number
• Perfect graphs with no balanced skew-partition are 2-clique-colorable
• The Grötzsch theorem for the hypergraph of maximal cliques

Cited in

(5)

• List-coloring graphs without \(K_{4,k}\)-minors
• The Grötzsch theorem for the hypergraph of maximal cliques
• A generalization of Grötzsch Theorem on the local-equitable coloring
• Thresholds for the monochromatic clique transversal game
• Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)

This page was built for publication: List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly

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