Pith. sign in

REVIEW

On the chromatic number of a family of odd hole free graphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2110.12710 v1 pith:2PKEGTZD submitted 2021-10-25 cs.DM math.CO

On the chromatic number of a family of odd hole free graphs

classification cs.DM math.CO
keywords holefreefullgraphhouseinducedchudnovskycolorable
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

A hole is an induced cycle of length at least 4, and an odd hole is a hole of odd length. A full house is a graph composed by a vertex adjacent to both ends of an edge in $K_4$ . Let $H$ be the complement of a cycle on 7 vertices. Chudnovsky et al [6] proved that every (odd hole, $K_4$)-free graph is 4-colorable and is 3-colorable if it does not has $H$ as an induced subgraph. In this paper, we use the proving technique of Chudnovsky et al to generalize this conclusion to (odd hole, full house)-free graphs, and prove that for (odd hole, full house)-free graph $G$, $\chi(G)\le \omega(G)+1$, and the equality holds if and only if $\omega(G)=3$ and $G$ has $H$ as an induced subgraph.

discussion (0)

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