pith. sign in

arxiv: 1408.3935 · v2 · pith:SADMVCY3new · submitted 2014-08-18 · 🧮 math.CO

Coloring clique-hypergraph of K₅-minor-free graphs

classification 🧮 math.CO
keywords graphclique-coloringcoloringclique-colorableclique-hypergraphcombineverygraphs
0
0 comments X
read the original abstract

A clique-coloring of a graph $G$ is a coloring of the vertices of $G$ so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, $\mathcal{H}(G)$, of a graph $G$ has $V(G)$ as its set of vertices and the maximal cliques of $G$ as its hyperedges. A (vertex) coloring of $\mathcal{H}(G)$ is a clique-coloring of $G$. The clique-chromatic number of $G$ is the least number of colors for which $G$ admits a clique-coloring. Every planar graph has been proved to be 3-clique-colorable (Electr. J. Combin. 6 (1999), \#R26). Recently, we showed that every claw-free planar graph, different from an odd cycle, is $2$-clique-colorable (European J. Combin. 36 (2014) 367-376). In this paper we generalize these results to \{claw, $K_5$-minor\}-free graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.