Clique‐coloring some classes of odd‐hole‐free graphs | Zendy

Défossez David | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Clique‐coloring some classes of odd‐hole‐free graphs

Author(s) -

Défossez David

Publication year - 2006

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.20177

Subject(s) - combinatorics , mathematics , split graph , chordal graph , perfect graph , graph coloring , clique number , cograph , discrete mathematics , block graph , clique sum , brooks' theorem , graph , clique graph , line graph , pathwidth , 1 planar graph , graph power

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C ‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K 4 ‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research