Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)

DOI10.1016/j.tcs.2015.05.030zbMath1331.05086OpenAlexW630596220MaRDI QIDQ500982

Erfang Shan, Li-ying Kang

Publication date: 8 October 2015

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

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

zbMATH Keywords

polynomial-time algorithmplanar graph\(K_5\)-subdivision-free graphclique-coloringclique-hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) 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)

Clique-coloring of \(K_{3,3}\)-minor free graphs ⋮ A linear-time algorithm for clique-coloring planar graphs ⋮ List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of clique coloring and related problems
• Clique-transversal sets of line graphs and complements of line graphs
• Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
• Chains, antichains, and fibres
• Two-colouring all two-element maximal antichains
• Covering the cliques of a graph with vertices
• The Grötzsch theorem for the hypergraph of maximal cliques
• The four-colour theorem
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Clique-transversal sets and clique-coloring in planar graphs
• Über eine Eigenschaft der ebenen Komplexe
• Clique-coloring some classes of odd-hole-free graphs
• Complexity of clique-coloring odd-hole-free graphs
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Sur le coloriage des graphs
• Colouring clique-hypergraphs of circulant graphs
• On the divisibility of graphs

This page was built for publication: Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)