Fractional cocoloring of graphs

Abstract: The cochromatic number

Z (G)

of a graph

G

is the fewest number of colors needed to color the vertices of

G

so that each color class is a clique or an independent set. In a fractional cocoloring of

G

a non-negative weight is assigned to each clique and independent set so that for each vertex

v

, the sum of the weights of all cliques and independent sets containing

v

is at least one. The smallest total weight of such a fractional cocoloring of

G

is the fractional cochromatic number

Z_{f} (G)

. In this paper we prove results for the fractional cochromatic number

Z_{f} (G)

that parallel results for

Z (G)

and the well studied fractional chromatic number

c h i_{f} (G)

. For example

Z_{f} (G) = c h i_{f} (G)

when

G

is triangle-free, except when the only nontrivial component of

G

is a star. More generally, if

G

contains no

k

-clique, then

Z_{f} (G) l e c h i_{f} (G) l e Z_{f} (G) + R (k, k)

. Moreover, every graph

G

with

c h i_{f} (G) = m

contains a subgraph

H

with

Z_{f} (H) g e (f r a c 14 - o (1)) f r a c m l o g_{2} m

. We also prove that the maximum value of

Z_{f} (G)

over all graphs

G

of order

n

is

T h e t a (n / l o g n)

, and the maximum over all graphs embedded on an orientable surface of genus

g

is

T h e t a (s q r t g / l o g g)

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Fractional cocoloring of graphs