2015/10/30 by Huang, Shenwei, da Silva, Murilo V. G.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1510.09192
A \em hole is a chordless cycle of length at least four. A hole is \em even (resp. \em odd) if it contains an even (resp. odd) number of vertices. A cap is a graph induced by a hole with an additional vertex that is adjacent to exactly two adjacent vertices on the hole. In this note, we use a decomposition theorem by Conforti et al. (1999) to show that if a graph G does not contain any even hole or cap as an induced subgraph, then χ(G)≤ \lfloor(3)/(2)ω(G)\rfloor, where χ(G) and ω(G) are the chromatic number and the clique number of G, respectively. This bound is attained by odd holes and the Hajos graph. The proof leads to a polynomial-time 3/2-approximation algorithm for coloring (even-hole,cap)-free graphs.