Equitable clique-coloring in claw-free graphs with maximum degree at most 4 (Q2657098)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equitable clique-coloring in claw-free graphs with maximum degree at most 4 |
scientific article |
Statements
Equitable clique-coloring in claw-free graphs with maximum degree at most 4 (English)
0 references
17 March 2021
0 references
A clique of a graph \(G\) is a set of pairwise adjacent vertices of \(G\). A clique on \(m\) vertices is called an \(m\)-clique of \(G\). A clique-coloring, also known as weak coloring, is an assignment of colors to the vertices of \(G\) in such a way that no inclusion-wise maximal clique of size at least two is monochromatic. An equitable vertex-coloring of \(G\) is a proper vertex-coloring such that any two color classes differ in size by at most one. An equitable clique-coloring of \(G\) is a clique-coloring such that any two color classes differ in size by at most one. If \(G\) has an equitable clique-coloring with \(k\) colors, we say that \(G\) is equitably \(k\)-clique colorable. The purpose of the paper is to show that every connected claw-free graph with maximum degree at most four, other than an odd cycle greater than three, is also equitably 2-clique-colorable, where the claw is the complete bipartite graph \(K(1;3)\). The paper also gives an algorithm for an equitable 2-clique-coloring in linear time for this class of graphs.
0 references
equitable clique-coloring
0 references
claw-free graph
0 references
linear time algorithm
0 references