A program to find families of graphs in Free$\{C_4,4K_1\}$ with bounded clique width
In this paper we study the class of graphs without cycles of size 4 and independent sets of size 4 as induced subgraphs: $\mathop{Free}\{C_4, 4K_1\}$. This is one of the three minimal minimal open cases for the complexity of the colouring problem when restricted to classes defined by excluding induced subgraphs of order 4. We investigate the clique width of some subclasses of $\mathop{Free}\{C_4, 4K_1\}$. We introduce a new framework: the $(k,l,m)$-decomposition and prove that if all the graphs of a class $\cal G$ are $(k,l,m)$-decomposable, then graphs in $\cal G$ have bounded clique width.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.17307
curl -X POST /api/v1/records/arxiv/2606.17307/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.17307/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'